Proof by Induction

[mendhak]

What is "Induction Hypothesis"?

This question has me stumped, any help?

We define the sequence L by L₀=5 and for k>=1,
L_k=2L_k-1-7.

a) Determine L₄ <--- This one I got.. duh

b) Prove by induction that L_k= 7-2^k+1

I can't figure out b. Any help appreciated. Thanks.

[krtxmrtz]

You verify it's true for k=1, then you try to prove that if it holds for k=n-1 then it will also hold for k=n.
Since n can be any number and it's true for k=1, then it must be true for k=2, and therefore for k=3, and then for k=4, and so on.

For your specific problem you first see it's true for k=1:

L₁ = 2L₀ - 7 = 3
and
L₁ = 7 - 2² = 3

Now assume it's true for k= n - 1, i.e. assume L_n-1 = 7 - 2ⁿ holds. Let's prove it for k=n. We must prove that L_n = 7 - 2ⁿ⁺¹

Indeed:

L_n = 2L_n-1 -7 = 2*(7 - 2ⁿ) - 7 =

(because we have ssumed the expression is valid for k = n-1)

= 14 - 2*2ⁿ - 7 = 7 - 2ⁿ⁺¹

[mendhak]

Originally posted by krtxmrtz
You verify it's true for k=1, then you try to prove that if it holds for k=n-1 then it will also hold for k=n.
Since n can be any number and it's true for k=1, then it must be true for k=2, and therefore for k=3, and then for k=4, and so on.

Thanks... I understood the solution. What I have quoted here, this is the actual 'induction hypothesis'? SO I can safely apply it to any question I see with the words "induction hypothesis" in there?

[krtxmrtz]

I have explained this induction hypothesis in my own words, perhaps it was not quite strict from the mathematical/philosophical point of view.

It may be worth a visit to http://www.bath.ac.uk/~ma1gpg/summatio.htm or try to search the words by means of altavista, google, askjeeves or any other search engine you like. You should find tons of information.

[mendhak]

OK, Thanks for the help.

[sql_lall]

Ok, i'm not sure if this will help or complicate the subject, but there is also a bigger, "Better" version of induction, called Strong Induction.

The induction mentioned by krtxmrtz was where you assume that it is true for k = n-1, and proove it for k = n

However, in Strong induction, you assume it is true for ALL k < n, and use this to proove for k = n