Lucas and Fibonacci Numbers

Question

Problem:

Let \begin{align*} A_0 &= 6 \\ A_1 &= 5 \\ A_n &= A_{n - 1} + A_{n - 2} \; \textrm{for} \; n \geq 2. \end{align*} There is a unique ordered pair $(c,d)$ such that $c\phi^n + d\widehat{\phi}^n$ is the closed form for sequence $A_n$.

Find $c$ using the Fibonacci and Lucas number sequences.

My Solution:

$A_n$ is just $3L_n$+$2F_n,$ where $L_n$ is the $n^{th}$ Lucas number and $F_n$ is the $n^{th}$ Fibonacci number. Since the closed form of the Fibonacci sequence is $$F_n = \frac{1}{\sqrt{5}} \left( \phi^n - \widehat{\phi}^n \right),$$ and the closed form of the Lucas sequence is $$L_n = \phi^n + \widehat{\phi}^n,$$ we get the closed form of $A_n$ as $\dfrac{2}{\sqrt{5}}+3.$

What is wrong with my solution?

EDIT: My answer is actually right.

Answer 1

Any sequence of the Fibonacci-type, i.e., $f_n=f_{n-1}+f_{n-2}$, can be expressed as a sum of a Fibonacci-term and a Lucas-term, as follows

$$f_n=\left(f_1-\frac{f_0}{2}\right) \frac{\phi^n-\psi^n}{\phi-\psi}+\frac{f_0}{2} (\phi^n+\psi^n) $$

where $\psi=-1/\phi$. For a more detailed description and generalization, see my post at Decimal Fibonacci Number?

Answer 2

Although the problem is old there are two additional methods that can be considered.

First Method

Given \begin{align*} A_0 &= 6 \\ A_1 &= 5 \\ A_n &= A_{n - 1} + A_{n - 2} \; \textrm{for} \; n \geq 2. \end{align*} then, since Fibonacci and Lucas numbers satisfy the difference equation, one can take $$A_{n} = b \, F_{n} + c \, L_{n}.$$ First note that $F_{n} = \{ 0, 1, 1, ...\}_{n\geq 0}$ and $L_{n} = \{2, 1, 3, ...\}_{n \geq 0}$. For $A_{0} = 6$ then $6 = 2 c$ or $c = 3$ and leads to $A_{n} = b F_{n} + 3 L_{n}$. For $A_{1} = 5 = b + 3$ then $b = 2$ and leads to $$A_{n} = 2 \, F_{n} + 3 \, L_{n}.$$ In terms of Fibonacci numbers only the solution is $A_{n} = 5 \, F_{n} + 6 \, F_{n-1}$.

Second Method

The generating function for $A_{n+2} = A_{n+1} + A_{n}$ takes the form $$\sum_{n=0}^{\infty} A_{n} \, t^{n} = \frac{A_{0} + (A_{1} - A_{0}) \, t}{1 - t - t^2}$$ and comparing to the generating function of the Fibonacci numbers, $$\sum_{n=0}^{\infty} F_{n} \, t^{n} = \frac{t}{1 - t - t^2},$$ and yields $$\sum_{n=0}^{\infty} A_{n} \, t^{n} = \sum_{n=0}^{\infty} (A_{0} \, F_{n+1} + (A_{1} - A_{0}) \, F_{n}) \, t^n$$ and yields the general form $$A_{n} = A_{0} \, F_{n+1} + (A_{1} - A_{0}) \, F_{n} = A_{1} \, F_{n} + A_{0} \, F_{n-1}.$$ This result agrees with the first.