Proof by Induction

[mendhak]

What is "Induction Hypothesis"?

This question has me stumped, any help?


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

a) Determine L4 <--- This one I got.. duh :p

b) Prove by induction that Lk= 7-2k+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:

L1 = 2L0 - 7 = 3
and
L1 = 7 - 22 = 3

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

Indeed:

Ln = 2Ln-1 -7 = 2*(7 - 2n) - 7 =

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

= 14 - 2*2n - 7 = 7 - 2n+1

[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