Mathematical Induction (Fibonacci sequence)

[Rob Hal]

Hi,

I'm looking for some help regarding a problem I have.
It's a problem I'm doing for my computer science class, and we need to prove certain conjectures using mathematical induction. Now, I've never learned mathematical induction in any class, so I'm basing everything I know about it off the course book.

So, I'm given the Fibonnaci sequence defined by the relation:
if k is 1 or 2, then f(k) = 1
else if k > 2, then f(k) = f(k-1) + f(k-2)

I have to do the following...
For the Fibonacci sequence, shot that, for all n>=2, f(n)2 + f(n-1)2 = f(2*n-1).
For the Fibonacci sequence, show that, for all n>2, f(n-1)*f(n+1) = f(n)2+(-1)n.

Okay, so I know I do it in three steps...
1. I do the basis, and I prove that for a certain value, it works out. I did that.
2. I assume that the conjecture works for a certain value, k. Okay.
3. I test to see if the conjecture works for a value k+1... Here is where I get stuck. I've been replacing n in both equations for k+1, but I'm not able to solve the equations. Am I doing something wrong? Should I try something else?

Any help will be much appreciated.
Thank you

 

[philosophking]

Wait a sec..

The way you have those set up, neither of the two things you have to prove are correct in the first place.

To make this a somewhat more constructive response (hehe), usually you prove recurrence relations (which is what the fibonnaci sequence is) with strong induction, a variant of mathematical induction. Do you know about that?

 

[Rob Hal]

The problem I am given asks this specifically:

"Use mathematical induction to prove each of the following conjectures. In your proofs, be sure to state clearly the base case, the induction hypotheses, and what you’re attempting to prove in the induction step. "

And the two equations I posted previously are exactly what we have to prove. They're supposed to be correct...

As for strong induction... I have no idea. Like I said earlier, mathematical induction is not something I have ever formally been taught. I've been using my course lecture notes as a guide to what I should be doing.

The methode I've been using has worked for a few other problems I had, but just not these two...

 

[philosophking]

f(1)=1
f(2)=1
f(3)=2

Consider the base case for your first proof

Let n=2. Then f(2)*2+f(1)*2 = f(3)
But (1)(2) + (1)(2) = 4, not f(3)=2

I don't think your notation is very clear. f(n)2 is seen to me as 2*f(n)

 

[HallsofIvy]

I suspect that, by "f(n)2 + f(n-1)2", Rob Hal means "f(n)²+ f(n-1)²".

 

[matt grime]

For strong induction (and induction too), you take, say f(n-1)f(n+1) you subs in what you think will help (f(k)=f(k-1)+f(k-2)) and rearrange, now whenever you get an expression f(k-1)f(k+1) where k<n (not just k=n-1) you may assume the result for k by induction. So you use the truth of (possbily) all (or some) of the statements indexed k where k<n. So if in your manipulations you ended up with

f(n-3)f(n-1) +f(n-5)f(n-3) you could replace that with f(n-1)f(n-1) + (-1)^{n-1} + f(n-4)f(n-4)+(-1)^{n-4}

 

[Rob Hal]

Yeah, I posted it wrong...

I copy pasted the equations and didn't realize that the ^ sign didn't go with them...

For the Fibonacci sequence, shot that, for all n>=2, f(n)^2 + f(n-1)^2 = f(2*n-1).
For the Fibonacci sequence, show that, for all n>2, f(n-1)*f(n+1) = f(n)^2+(-1)^n.

My mistake.

 

[Rob Hal]

How 'bout this...

Perhaps it would be easier if I tried to see what I'm doing wrong with a simpler problem. (or at least, one that looks like it should be simple to me)

So show that n^5 - n is divisible by 5 for all n > 0.

Okay, so I can easily prove the basis by substituting in any number.

So, for n = k, it holds that k^5-k is divisible by 5

Now, I let n = k + 1 to prove by it...
So I have (k+1)^5 - (k+1)
And that is equal to k^5 +5*k^4+9*k^3+9*k^2+5*k - k.
To prove that it would be divisible by 5, I can group (k^5-k) together and 5(k^4 + k) together... problem is, I'm left with 9*k^3 + 9*k^2 which I can't prove is divisible by five...

So I based this off of an example I had, although slightly different... I think I may be completely off here.

 

[matt grime]

Erm, you might find it easier if you worked out 5C2 correctly.

 

[Rob Hal]

Hoooo boy... yeah, that was bad.
Okay. Then I am on the right track.
Thanks!

 

[uart]

For the Fibonacci sequence, show that, for all n>=2, f(n)^2 + f(n-1)^2 = f(2*n-1).

That one stumped while trying to work from left to right, then I tried starting with the RHS and it suddenly seemed to come out dead easy.

Start by using repeated applications of the defining recursion forumla on f(2n-1) (and induction on k) to show that,

f(2n-1) = f(k)*f(2n-k) + f(k-1)*f(2n-k-1)

Suddenly it was too easy. :)

 

[matt grime]

Same with a lot of induction problems. I started the other one several times and it didn't drop out until I picked a non-obvious move and it worked in a line. non-obvious means that because of the way it's written we try and get f(k-1)f(k+1) and subs for that for k<n, (we work left to right) but actually if you get a f(k)f(k) for some k<n then subs in from there it comes out all of a sudden.