# Strong induction on Fibonacci numbers

#### TheFangel

Hi,

today I'm really stuck with strong inductions...

Let $$\displaystyle F_n$$ be the $$\displaystyle n^{th}$$ Fibonacci number. Prove that for all m ≥ 1 and all n, $$\displaystyle F_{m+n} = F_{m-1} F_n + F_m F_{n+1}$$.

Can someone help me with it?

#### wonderboy1953

Response

Recently got a book by Posamentier on Fibonacci numbers that I believe discusses strong induction on them. I'll look it up when I get home and let you know what I find out.

Question for you. Have you tried Googling for an answer?

#### TheFangel

Question for you. Have you tried Googling for an answer?
Yes I tried but this particular proof is not explained. I can only find the strong induction proof of the fibonacci numbers defined as $$\displaystyle F_n = F_{n-1} + F_{n-2}$$ with $$\displaystyle F_0 = 0$$ and $$\displaystyle F_1 = 1$$ with $$\displaystyle n \ge 2$$.

Thank you very much!

Hi,

today I'm really stuck with strong inductions...

Let $$\displaystyle F_n$$ be the $$\displaystyle n^{th}$$ Fibonacci number. Prove that for all m ≥ 1 and all n, $$\displaystyle F_{m+n} = F_{m-1} F_n + F_m F_{n+1}$$.

Can someone help me with it?
Hi The Fangel,

P(k)

$$\displaystyle F_{m+k}=F_{m-1}F_k+F_mF_{k+1}$$

P(k+1)

$$\displaystyle F_{m+k+1}=F_{m-1}F_{k+1}+F_mF_{k+2}$$

Proof

$$\displaystyle F_{k+1}=F_k+F_{k-1}\ \Rightarrow\$$$$\displaystyle F_k=F_{k+1}-F_{k-1}$$

and

$$\displaystyle F_{k+2}=F_{k+1}+F_k\ \Rightarrow\ F_{k+1}=F_{k+2}-F_k$$

then it follows

$$\displaystyle F_{m+k+1}=F_{m+k}+F_{m+k-1}$$

$$\displaystyle =F_{m-1}F_k+F_mF_{k+1}+F_{m+k-1}$$

$$\displaystyle =F_{m-1}F_{k+1}-F_{m-1}F_{k-1}+F_mF_{k+2}-F_mF_k+F_{m+k-1}$$

$$\displaystyle =F_{m-1}F_{k+1}+F_mF_{k+2}+\left(F_{m+k-1}-F_mF_k-F_{m-1}F_{k-1}\right)$$

as the part in brackets is zero based on P(k), then

$$\displaystyle F_{m+k+1}=F_{m-1}F_{k+1}+F_mF_{k+2}+0$$

• TheFangel

#### wonderboy1953

• TheFangel

#### TheFangel

Thank you very much to both of you!

In the end I chose the one of wonderboy because it shows in a clearer way the strong induction mechanism, even though both are very valid.