Who Doesn't Like Recursion and Math?

[bryangoodrich]

So my CS class on discrete math, of which the teacher is far from expert, had a problem today the teacher basically had to blow off because it was a proof by induction ... that didn't use induction lol

Let f be the Fibonacci sequence,
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2), for all n > 1

Then prove for n > 1 that

\(P(n) := f(n+1)^2 - f(n)^2 = f(n-1)\times f(n+2)\)

The base cases are easy

For n = 2

\(f(3)^2 - f(2)^2 = 2^2 - 1^2 = 4 - 1 = 3\)
\(f(1)\times f(4) = 1 \times 3 = 3\)

Similarly for n = 3 (P(n) = 5).

So we assume that the statement P(n) is true of n. Technically, I should substitute 'k' or something, but there's no need as I think it's clear what variable we're labeling.

We want to show (WTS) that P(n+1) is true, expressed by (after simplifying)

\(P(n+1) := f(n+2)^2 - f(n+1)^2 = f(n)\times f(n+3)\)

At some point, you must use the induction assumption, either directly or through some sort of substitution. I find this EXTREMELY difficult because there's so many forms of this function to relate. I mean, any f(k) can be rewritten as a sum of some offset of f(k)--e.g., f(n+1) = f(n) + f(n-1) AND f(n+1) = f(n+3) - f(n+2). Tricky!! To complicate matters even more, we have to deal with the squaring of f.

I spent all class trying to find an innovative way to intuit the solution, but I couldn't. Writing this out here has given me some ideas, but I figured I'd share the misery ... I mean joy!

 

[bryangoodrich]

I spent way too much time on this problem -_-

I think it requires strong induction instead of weak induction. The difference being

Assume P(1), P(2), P(3), ..., P(n), prove P(n+1). In weak induction, you just assume P(n) and cannot access P(n-1), P(n-2), ... assumed truths. This is why proofs like this require more base cases, to cover the "n-1", etc. statements. You prove for some 1, ..., k number of cases to access P(n-1), ..., P(n-k) additional assumed truths. They carry the same logical strength, but the latter gives you access to more content that can make proofs easier.

I'm not sure if this proof requires it, but it may help. I can't figure out where, though. I keep trying to work on the LHS and reduce the squares out, but I end up with a 2f(n-1)f(n) type statement that doesn't help because then I cannot figure out how to pull out an opposing one to remove such a beast. I've tried working from the RHS which seems more straight-forward, but I still can't get anywhere. E.g.,

\(f(n)f(n+3) = f(n)f(n+2) + f(n)f(n+1)\)

What next?! It's no longer in a 3-offset like in P(n). So expand f(n)? Seems like the only option.

\(f(n-1)f(n+2) + f(n-2)f(n+2) + f(n-1)f(n+1) + f(n-2)f(n+1)\)

Does this help? It gives access to some P(.) statements

\(P(n) + f(n-2)f(n+2) + f(n-1)f(n+1) + P(n-1)\)

Okay, so we can throw in some squares and zero out canceling terms

\(f(n+1)^2 - f(n)^2 + f(n)^2 - f(n-1)^2 + f(n-2)f(n+2) + f(n-1)f(n+1)\)

So I'm stuck here on this course of action ...

\(f(n+1)^2 - f(n-1)^2 + f(n-2)f(n+2) + f(n-1)f(n+1)\)

There's almost a nice symmetry to this, but I can't see how it or anything can help me at this point. The induction assumption(s) aren't useful now. Any thoughts?

 

[Dason]

\(f(n+3)^2 - f(n+2)^2 = [f(n+3) + f(n+2)][f(n+3) - f(n+2)] = \)
\( [f(n+4) - f(n+2) + f(n+2)][f(n+3) - (f(n+3) - f(n+1))] = f(n+4)f(n+1)\)

Do we really need induction?

 

[bryangoodrich]

No, I solved it today. It shouldn't be solved by induction. It's a direct proof, quite easy once you see how the pieces fall together.

Let \(n > 0, n\in \mathbb{N}\). Prove \(P(n): f_{n+1}^2 - f_{n}^2 = f_{n-1}f_{n+2}\)
\(f_{n+1}^2 - f_{n}^2 = (f_{n} + f_{n-1})^2 - f_{n}^2\)
\(= (f_{n}^2 + f_{n-1}^2 + 2f_{n}f_{n-1}) - f_{n}^2\)
\(= f_{n-1}^2 + 2f_{n}f_{n-1}\)
\(= f_{n-1}f_{n-1} + f_{n}f_{n-1} + f_{n}f_{n-1}\)
\(= f_{n-1}(f_{n}+f_{n-1}) + f_{n}f_{n-1}\)
\(= f_{n-1}f_{n+1} + f_{n}f_{n-1}\)
\(= f_{n-1}(f_{n+1} + f_{n})\)
\(= f_{n_1}f_{n+2}\)
QED.

 

[noetsi]

In answer to the original question...I would say about 98 percent of the US population

 

[Dason]

In answer to the original question...I would say about 98 percent of the US population

I wish you were wrong but you have a point.

 

[noetsi]

Sadly I do...based on painful experience (and cross national data).

I think raptors ate a far higher percentage of our (american) ancestors who were good with math

 

[soxi]

Nice. I think the most spare statement would be:

Let: \(f(x) = f(x-1) + f(x-2)\)

Prove: \(f^2(x+1) - f^2(x) = f(x+2) \times f(x-1)\)

These seem irrelevant:

• Fibonacci sequence
• \(f(0)\)
• \(f(1)\)
• \(x \in \{ {2, 3, 4, 5, 6, ...} \}\)
• interpretation of \(f^2(x+1) - f^2(x)\)

 

[noetsi]

So tempting....