Strong mathematical induction, how do u figure out the range of the variable?

[mr_coffee]

Hello everyone.

I've been looking at examples and I can't seem to see what they are doing.

For example, the book has:

Suppose that d1, d2, d3 ... is a sequence defined as follows:
d1 = 9/10, d2 = 10/11.

dk = dk-1 * dk-2 for all inegers k >= 3.

Prove that dn =< 1 for all integers n >= 0.

The book says:
Proof (by strong mathematical induction): let the property P(n) be the inequality dn =< 1.

Show that the proeprty is true for n = 1, and n =2:
I understand why they are starting at n = 1, but why are they testing 2 cases? If i had say, d1 = 9/10, d2 = 10/11, d3 = 10/12, then would i have to test for n = 1, n = 2, and n = 3?

They then go onto say,
Show that for any integer k > 2, if the property is true for all integeers i with 1 =< i < k, then it is true for k:

I'm confused on how they are getting k > 2, also how did they figure out that range from 1 = < i < k ?

My problem looks very similar to this one, but it has 3 subscripts instead of one:

http://suprfile.com/src/1/3itfbah/3.jpg



I would think k >= 3, because that's the problem states, that
ek = ek -1, ek-2, ek-3 for all integers k >= 3

THanks!

 

[matt grime]

They test for two start cases because you need to specify d_1 and d_2 in order to determine the rest of the sequence. d_n is defined in terms of the two previous terms, so you're never going to infer anything about the second term from the first alone.

Strong induction is very simple. You just use it when in order to deduce the veracity of P(n) you need to use more than just the previous term. If you can deduce it from the previous r terms for all n, then you need to verify it for the initial r terms. Note your example of d_1, d_2 and d_3 is silly. They don't satisfy d_n = d_{n-1}*d_{n-2}, do they? (please avoid using dk for the k'th term because dk-1 strictly means (dk) minus 1, not the k-1'st term).

 

[mr_coffee]

I do see what your saying matt,
but I'm still confused on why they said, for any integer k > 2, when in the problem it says, k >= 3 ? or is that equivlent because they are integers, so they can't use for example, 2.4, they would have to use 3?

 

[matt grime]

Of course it is equivalent. Unless you know of any integers between 2 and 3 exclusive?