another inductive proof

S

shakalandro

New member
Joined
Nov 29, 2008
Messages
36
Let u[sub:21min9po]n[/sub:21min9po] be the nth fibonacci number. Prove, by induction on n (without using the Binet formula) that

u[sub:21min9po]m+n[/sub:21min9po] = u[sub:21min9po]m-1[/sub:21min9po]u[sub:21min9po]n[/sub:21min9po] + u[sub:21min9po]m[/sub:21min9po]u[sub:21min9po]n+1[/sub:21min9po]

for all positive integers m and n.

Deduce, again using induction on n, that u[sub:21min9po]m[/sub:21min9po] divides u[sub:21min9po]mn[/sub:21min9po]
 
Start with n = 0 and verify (I'll leave that to you)

Now use the WEAK law of Induction:

Assume true for all k < n. [Not just for k = n-1]

u[m+k] = u[m-1]u[k] + u[m]u[k+1] for all k < n << the for all makes it the weak law.

Prove

u[m+n] = u[m-1]u[n] + u[m]u[n+1]

u[m+n] = u[m+n-1] + u[m+n-2]


u[m+n-1] = u[m-1]u[n-1] + u[m]u[n] << by assumption
u[m+n-2] = u[m-1]u[n-2] + u[m]u[n-1]<< by assumption
-------------------- ADD ------------------
u[m+n] = u[m-1]u[n-1] + u[m]u[n] + u[m-1]u[n-2] + u[m]u[n-1]

Factor, etc:

u[m+n] = u[m-1](u[n-1] + u[n-2]) + u[m](u[n] + u[n-1])

You can finish up.
 
daon said:
Start this inductive proof with n=1.
Click to expand...

I think the custom is to write the Fibonacci sequence as starting with

F[0] = 0
F[1] = 1
and then
F[n] = F[n-1] + F[n-2]

That's why I wrote to start at n = 0. Naturally you could do it starting at n = 1, and having the sequence go:

F[1] = 1
F[2] = 1
and then
F[n] = F[n-1] + F[n-2]

But starting as I suggested makes the 'base case' so simple even a cave-man could do it. (Please don't send me any letters.)
 
You're right, but I was merely pointing out the problem states that m and n are positive.
 
Okay, I understand the first part completely now, but how would one prove that u[sub:1nixemjj]m[/sub:1nixemjj] | u[sub:1nixemjj]mn[/sub:1nixemjj]
 
Show the initial case.

Assume \(\displaystyle u_m | u_{mn}\).

WTS: \(\displaystyle u_{m} | u_{m(n+1)}\).

Use the first proposition:

[1] ... \(\displaystyle u_{m(n+1)} = u_{mn+m} = u_{mn-1}u_{m} + u_{mn}u_{m+1}\)

By our I.H., \(\displaystyle u_{mn} = k*u_{m}\)

Substituting into [1], we have:

[2] ... \(\displaystyle u_{m(n+1)} = u_{mn-1}u_{m} + k*u_mu_{m+1} = u_m(u_{mn-1}+k*u_{m+1})\)

Got it?
 
shakalandro said:
Let u[sub:2l4kabps]n[/sub:2l4kabps] be the nth fibonacci number. Prove, by induction on n (without using the Binet formula) that

u[sub:2l4kabps]m+n[/sub:2l4kabps] = u[sub:2l4kabps]m-1[/sub:2l4kabps]u[sub:2l4kabps]n[/sub:2l4kabps] + u[sub:2l4kabps]m[/sub:2l4kabps]u[sub:2l4kabps]n+1[/sub:2l4kabps]

for all positive integers m and n.

Deduce, again using induction on n, that u[sub:2l4kabps]m[/sub:2l4kabps] divides u[sub:2l4kabps]mn[/sub:2l4kabps]
Click to expand...

Yes, that makes perfect sense, thankyou, it seems so easy afterwards
Click to expand...

And you did not have to do anything to have it solved!
 
You must log in or register to reply here.
Top