Recognitions:

## Strong Induction

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 $$P(1)$$ is true and $$P(k)$$ is true for all $$k \leq n \Rightarrow P(n+1)$$ is true then $$P(n)$$ is true for all $$n \in \mathbb{Z^+}$$

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

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

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

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 $$n \leq k$$ ? 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 $$n \leq k$$
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.
 PhysOrg.com mathematics news on PhysOrg.com >> Pendulum swings back on 350-year-old mathematical mystery>> Bayesian statistics theorem holds its own - but use with caution>> Math technique de-clutters cancer-cell data, revealing tumor evolution, treatment leads
 Recognitions: Science Advisor 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.
 Recognitions: Science Advisor 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.

Recognitions:
Homework Help