Strong Induction

disregardthat

Hi, I am trying to learn strong induction, but I am a bit uncertain in some things about it.

In my book, it says it states that: If [tex]P(1)[/tex] is true and [tex]P(k)[/tex] is true for all [tex]k \leq n \Rightarrow P(n+1)[/tex] is true then [tex]P(n)[/tex] is true for all [tex]n \in \mathbb{Z^+}[/tex]

Where P(n) is a preposition for an integer n.

Now, if we were to prove that if [tex]a_1=1, \ a_2=2[/tex] and [tex]a_{n+1}=\frac{a_n ^2}{a_{n-1}[/tex] for all [tex]n \leq 1[/tex], then [tex]a_n=2^{n-1}[/tex]

The way the book advance is to prove that [tex]P(1)[/tex] is true, and then assume that it is true for all [tex]n \leq k[/tex]. Then [tex]a_r=2^{r-1}[/tex] for [tex]r=1,2,3,...,k [/tex]

Then they prove it by assuming that it is true for k-1.

To the questions:

What does it actually mean to assume that it is true for [tex]n \leq k[/tex] ? Is it because it is true for 1 and 2, and therefore we have at two values, where we can for example let k=2 and k-1=1?

Could we have completed the proof by only showing that P(1) is true? Could we then have assumed that it was true for r=1,2,3,...k, and then proven it by assuming it was true for k-1? Or is it vital that we know at least TWO values before proceeding with this?

I read that this form of induction is far stronger than the weak form. But later on it says that it is logically equivalent. To me both methods seem very alike. But is all there is to strong induction that we must have more than 1 value to prove that it is true for all values?

I don't really understand the way they assume it is true for [tex]n \leq k[/tex]
But i do understand the concept of induction. It is the way they explain strong induction that sets me a bit off.

Hm, this may be a little confusing, but I would really appreciate if someone could explain it to me.

mathman

It is a rather simple concept. The basic rules are P(1) is true and P(n) true implies P(n+1) true,
leading to the conclusion P(n) is true for all n.

To understand it, start at n=1, since P(1) is true then P(2) is true. Since P(2) is true then P(3) is true. You just keep going and you get P(n) is true for all positive n.

disregardthat

Yeah, of course. That's the weak form, which I understand. It's a simple concept as you say. But I don't see the difference between the weak and the strong.

CRGreathouse

They seem different to most people, since weak induction assumes only that the n-1 caseholds and strong induction assumes that cases 1, 2, 3, ..., n-1 hold. But they are equivalent, so there really isn't a difference.

disregardthat

Thanks for the answers. Now, if I have understood it right:
Weak induction is basically to prove that a statement is true for an integer, and then by assuming it is true for an integer k, follows that it is true for an integer k+1 and thus true for all integers above the starting integer. My way of thinking: If you set k=1, then it follows that it must be true for 1+1=2, by then setting k=2, it must be true for 2+1=3. By this train of thought it must be true for all successive integers above the starting integer.
Strong induction on the other hand is to prove that a statement is true for an integer, and then assume it is true for all integers between this and k. Then you prove by assuming this that if it is true for these integers, it must be true for k+1, and thus it must be true for all integers above the starting integer. My way of thinking: If you assume it is true for k, then it follows that it is true for k+1. Then you can set k=1 and by that it must be true for all successive integers. Now, in my mind, if you are to prove, say something about the fibonacci sequence, and you use that the statement is true for an integer k-1, then you must have proven it for TWO starting integers. For example if you prove it for 1 and 2. Then you can set k=2 and as proven by using the statement for k-1=1, and that it from that follows that it must be true for all successive integers.

But basically these two methods of induction are logically equivalent.

Have I got it right? It's quite important to me to understand what I learn.