Proving the Fibonacci Recurrence

Question

Following is out homework problem. And I have no clue how to do it. The strong induction one seems doable, but a is a nightmare. I have done all sorts of weird things over the past week, including somehow reaching a conclusion that the sum of two consecutive Fibonacci numbers is linked to the sum of the binomial coefficients at a certain power (haven’t worked out the exact relationship but there’s definitely something there).In short, I’ve done a lot, just not actually solving the problem. Can someone help me?

induction recurrence relations recursive algorithms

Brian M. Scott · Answer

HINT for (a): You need to use an induction hypothesis that is stronger than the obvious one.

$P(n)$: For all $c,dinBbb R$, $f(n;c,d)=f(n-1;c,d)+f(n-2;c,d)$.

In the induction step you’ll apply this induction hypothesis with $c=b$ and $d=a+b$.

Proving the Fibonacci Recurrence

One Answer

Add your own answers!

Ask a Question