Solving Recurrent Relations using Backtracking

Question

The following formula has been provided:

$a(n) = a(n-1) + a(n-2)\quad \mbox{with initial states}\quad 0 , 2 $

After some research the formula is found to be a Binet's Formula.

It is required to convert the above recursive formula to an explicit formula using the Backtracking method.

This is what i have done: \begin{align} a(n) &= a(n-1) + a(n-2) = (a(n-2) + a(n-3)) + a(n-2) \\ & = 2a(n-2) + a(n-3) = 2(a(n-3) + a(n-4)) + a(n-3) \\ & = 3a(n-3) + 2a(n-4) = 3(a(n-4) + a(n-5)) + 2a(n-4) \\ & = 5a(n-4) + 3a(n-5) = 5(a(n-5) + a(n-6)) + 3a(n-5) \\ & = 8a(n-5) + 5a(n-6) \\ & \vdots \\ & \mbox{and so on}\ldots \end{align}

As it can be seen, there is a relationship with Pascal triangle.

Answer 1

Hint: It looks like $a(n) = b(k)a(n-k)+b(n-1)a(n-k-1) $ for some sequence $b(k)$. Find the recurrence satisfied by $b(k)$.

Then set $k=n-1$.

Answer 2

If $a(n) = a(n-1) + a(n-2) $, then $a(n)=a(1)F_n + a(0) F_{n-1}$,where $F_n$ is the $n$-th Fibonacci number. (Use $F_{-1}=1$.)

Here is a roadmap for a proof:

• Let $b(n)=a(1)F_n + a(0) F_{n-1}$.
• Prove that $b(n) = b(n-1) + b(n-2)$
• Prove that $b(1)=a(1)$ and $b(0)=a(0)$.
• Conclude that $b(n)=a(n)$ for all $n$.