Hello.

I am stuck on a homework problem.

"Let U(subscript)n be the nth Fibonacci number. Prove by induction on n (without referring to the Binet formula) that U(subscript)m+n=U(subscript)m-1*U(subscript)n + U(subscript)m *U (subscript)n+1 for all positive integers m and n.

So.. I figured out my Base case for n=1.
Um+1=Um-1*U1+Um*U2, which equals Um+1=Um-1+Um, so it is true.

For the Induction Step, I dont know where to go..

Should I prove it P(K-1)--> P(K) or P(K)--> P(K+1).

I've been trying both ways and I am stuck on everything.

2. Originally Posted by Laurali224
Hello.

I am stuck on a homework problem.

"Let U(subscript)n be the nth Fibonacci number. Prove by induction on n (without referring to the Binet formula) that U(subscript)m+n=U(subscript)m-1*U(subscript)n + U(subscript)m *U (subscript)n+1 for all positive integers m and n.

So.. I figured out my Base case for n=1.
Um+1=Um-1*U1+Um*U2, which equals Um+1=Um-1+Um, so it is true.

For the Induction Step, I dont know where to go..

Should I prove it P(K-1)--> P(K) or P(K)--> P(K+1).

I've been trying both ways and I am stuck on everything.
What's the Binet formula?

3. Binet Formula- The Fibonacci numbers are given by the following formula:

U(subscript)n=(alpha^n-Beta^n)/square root of 5.

where alpha= (1+square root of 5)/2 and Beta=(1-square root of 5)/2.

4. Originally Posted by Laurali224
Binet Formula- The Fibonacci numbers are given by the following formula:

U(subscript)n=(alpha^n-Beta^n)/square root of 5.

where alpha= (1+square root of 5)/2 and Beta=(1-square root of 5)/2.
Haha, that is what I was going to do. I'll let another member work through this, and if no one does by the time I come back I'll give it a go.

5. k thanks.

So far I have for the Inductive Part-

Hypothesis..

If U(subscript) m+k-1= U(subscript)m-1*U(subscript)k-1 + U(subscript)m * U(subscript)k THEN U(sub)m+k=U(sub)m-1* U(sub)k +U(sub)m *U(sub)k+1.

So I am working with P(k-1)--> P(k) ...

SO I want to show [U(sub)m+k=U(sub)m-1* U(sub)k +U(sub)m *U(sub)k+1] is true.

So I began with U(sub) m+k=U(sub)m+k+1 + U(sub) m+k-2. But I think I am already lost.

6. Let n = 1, and consider $\displaystyle U_1 = U_2 = 1, U_3 = 2$.

Then the rule given says $\displaystyle U_{m+1} = U_{m-1} \cdot U_1 + U_m \cdot U_2$; that is

$\displaystyle U_{m+1} = U_{m-1} + U_m$, which is true.

Also $\displaystyle U_{m+2} = U_{m-1} \cdot U_2 + U_m \cdot U_3$;

$\displaystyle U_{m+2} = U_{m-1} + 2 \cdot U_m = (U_{m-1} + U_m) + U_m = U_{m+1} + U_m$ and the first step is complete.

Now suppose $\displaystyle U_{m+k} = U_{m-1} \cdot U_k + U_m \cdot U_{k+1}$ is true for all $\displaystyle k \leq n$.

Then (1) $\displaystyle U_{m+n-1} = U_{m-1} \cdot U_{n-1} + U_m \cdot U_n$ and

(2) $\displaystyle U_{m+n}= U_{m-1} \cdot U_n + U_m \cdot U_{n+1}$.

Now by the recursion, $\displaystyle U_{m+n+1} = U_{m+n-1} + U_{m+n}$,

which is, according to the formulas (1) and (2) above:

$\displaystyle U_{m-1} \cdot U_n + U_m \cdot U_{n+1} + U_{m-1} \cdot U_{n-1} + U_m \cdot U_n =$

$\displaystyle U_{m-1} \cdot (U_n + U_{n-1}) + U_m \cdot (U_{n+1} + U_n) =$ (according to the recursion)

$\displaystyle U_{m-1} \cdot U_{n+1} + U_m \cdot U_{n+2}$,

and the induction is complete.

7. Hi Laurali224,

$\displaystyle U_{m+k}=U_{m-1}U_k+U_mU_{k+1}$ ?

If so, then the following should be true

$\displaystyle U_{m+k+1}=U_{m-1}U_{k+1}+U_mU_{k+2}$

Hence, we try to prove that by using the equation on the first line.

Since $\displaystyle U_k=U_{k+1}-U_{k-1}$ and $\displaystyle U_{k+1}=U_{k+2}-U_n$

then

$\displaystyle U_{m+k+1}=U_{m+k}+U_{m+k-1}=U_{m-1}U_k+U_mU_{k+1}+U_{m+k-1}$

$\displaystyle =U_{m-1}U_{k+1}-U_{m-1}U_{k-1}+U_mU_{k+2}-U_mU_k+U_{m+k-1}$

$\displaystyle =U_{m-1}U_{k+1}+U_mU_{k+2}+\left(U_{m+k-1}-U_mU_k-U_{m-1}U_{k-1}\right)$

which is true given that we must have $\displaystyle U_{m+k-1}=U_mU_k+U_{m-1}U_{k-1}$