# Need help deriving recurrence relation for even-valued Fibonacci numbers.

That would be every third Fibonacci number, e.g. $0, 2, 8, 34, 144, 610, 2584, 10946,...$

Empirically one can check that:

$a(n) = 4a(n-1) + a(n-2)$ where $a(-1) = 2, a(0) = 0$.

If $f(n)$ is $\operatorname{Fibonacci}(n)$ (to make it short), then it must be true that $f(3n) = 4f(3n - 3) + f(3n - 6)$.

I have tried the obvious expansion:

$f(3n) = f(3n - 1) + f(3n - 2) = f(3n - 3) + 2f(3n - 2) = 3f(3n - 3) + 2f(3n - 4)$ $= 3f(3n - 3) + 2f(3n - 5) + 2f(3n - 6) = 3f(3n - 3) + 4f(3n - 6) + 2f(3n - 7)$ ... and now I am stuck with the term I did not want. If I do add and subtract another $f(n - 3)$, and expand the $-f(n-3)$ part, then everything would magically work out ... but how should I know to do that? I can prove the formula by induction, but how would one systematically derive it in the first place?

I suppose one could write a program that tries to find the coefficients x and y such that $a(n) = xa(n-1) + ya(n-2)$ is true for a bunch of consecutive values of the sequence (then prove the formula by induction), and this is not hard to do, but is there a way that does not involve some sort of "Reverse Engineering" or "Magic Trick"?

-
Why isn't $f_{n+2}=3f_n-f_{n-2}$ suitable? – J. M. Dec 27 '11 at 4:31
@J.M., sorry I do not understand. If I were to expand $f_{n+2}$ the way I do it, I would end up with $2f_n + f_{n - 2} + f_{n - 3}$. Again, I can make this work if I know what I am trying to get. I wonder if you have read the question correctly - I am looking for even-valued (not even-indexed) fib numbers. If my assumption is mistaken, then sorry. However, I am not sure how to systematically arrive at a relation you have given and how to use it to help me simplify things. – Job Dec 27 '11 at 4:45
It seems I did misunderstand you (and I apologize for this); have you looked at the references here by any chance? – J. M. Dec 27 '11 at 4:50

The definition of $F_n$ is given:

• $F_0 = 0$
• $F_1 = 1$
• $F_{n+1} = F_{n-1} + F_{n}$ (for $n \ge 1$)

Now we define $G_n = F_{3n}$ and wish to find a recurrence relation for it.

Clearly

• $G_0 = F_0 = 0$
• $G_1 = F_3 = 2$

Now we can repeatedly use the definition of $F_{n+1}$ to try to find an expression for $G_{n+1}$ in terms of $G_n$ and $G_{n-1}$.

\begin{align*} G_{n+1}&= F_{3n+3}\\ &= F_{3n+1} + F_{3n+2}\\ &= F_{3n-1} + F_{3n} + F_{3n} + F_{3n+1}\\ &= F_{3n-3} + F_{3n-2} + F_{3n} + F_{3n} + F_{3n-1} + F_{3n}\\ &= G_{n-1} + F_{3n-2} + F_{3n-1} + 3 G_{n}\\ &= G_{n-1} + 4 G_{n} \end{align*}

so this proves that $G$ is a recurrence relation.

-

At André's request, I've decided to write an answer. I've also arbitrarily decided to be ambitious and greedy, and I will thus derive a recurrence for the $k$-th increment Fibonacci number $f_{kn}$. (For OP's specific case, $k=3$)

$$f_{kn}=\frac{\phi^{kn}-(-\phi)^{-kn}}{\sqrt 5}$$

Letting $u=\phi^k$ and $v=\left(-\dfrac1\phi\right)^k$, the formula takes the form

$$f_{kn}=pu^n+qv^n$$

This means that the characteristic polynomial for the recurrence satisfied by $f_{kn}$ takes the form

\begin{align*} x^2-(u+v)x+uv&=x^2-\left(\phi^k+\left(-\frac1\phi\right)^k\right)x+\left(\phi^k\left(-\frac1\phi\right)^k\right)\\ &=x^2-\left(\phi^k+\left(-\frac1\phi\right)^k\right)x+(-1)^k \end{align*}

and the recurrence itself goes like

$$f_{k(n+1)}=\left(\phi^k+\left(-\frac1\phi\right)^k\right)f_{kn}-(-1)^k f_{k(n-1)}$$

You might say that the form $\ell_k=\phi^k+\left(-\dfrac1\phi\right)^k$ is a bit unwieldy, and I agree. There are two ways to go about (slightly) simplifying this. One way makes use of the Newton-Girard formulae. These formulae express $\ell_k$ in terms of $\phi-\dfrac1\phi=1$ and $\phi\left(-\dfrac1\phi\right)=-1$. To use $k=3$ as an example:

$$\alpha^3+\beta^3=(\alpha+\beta)^3-3(\alpha+\beta)(\alpha\beta)$$

Making the replacement $\alpha+\beta=1$ and $\alpha\beta=-1$, we have

$$\ell_3=(1)^3-3(1)(-1)=4$$

The slick way is to recognize that since $\ell_k$ is itself a linear combination of $\phi^k$ and $\left(-\dfrac1\phi\right)^k$, it also satisfies the Fibonacci recurrence:

$$\ell_{k+1}=\ell_k+\ell_{k-1}$$

The $\ell_k$ are in fact the (not-so-famous) Lucas numbers. With $\ell_0=2$ and $\ell_1=1$, we have the sequence $2, 1, 3, 4, 7, 11,\dots$

In short, the recurrence is of the form

$$f_{k(n+1)}=\ell_k f_{kn}-(-1)^k f_{k(n-1)}$$

For $k=3$, we have $f_{3(n+1)}=\ell_3 f_{3n}-(-1)^3 f_{3(n-1)}$ or $f_{3(n+1)}=4 f_{3n}+f_{3(n-1)}$.

-
Very nice post. This is the kind of solution where each piece falls nicely at its right place. – Did Dec 27 '11 at 9:35
It turns out that the identity derived here is listed in the Wolfram Functions site. – J. M. Dec 28 '11 at 0:21
@JM: this identity is a special case of the identity $$F_{n+2k}=L_kF_{n+k}-(-1)^kF_n$$ However, the indices do not need to be multiples of $k$, they just need to differ by $k$. – robjohn Jan 16 '12 at 19:43

Let $\alpha$ and $\beta$ be the two roots of the equation $x^2-x-1=0$. Then the $n$-th Fibonacci number is equal to $$\frac{\alpha^n-\beta^n}{\sqrt{5}}.$$

We are interested in the recurrence satisfied by the numbers $$\frac{\alpha^{3n}-\beta^{3n}}{\sqrt{5}}.$$

If $x$ is either of $\alpha$ or $\beta$, then $x^2=x+1$. Multiply by $x$. We get $x^3=x^2+x=2x+1$. It follows that $x^4=2x^2+x=3x+2$. But then $x^5=3x^2+2x=5x+3$, and then $x^6=5x^2+3x=8x+5$.

We want $x^6=Ax^3+B$, where $A$ and $B$ are rational, indeed integers. So we want $8x+5=A(2x+1)+B$. Reading off $A$ and then $B$ is obvious: we need $A=4$ and $B=1$.

So the numbers $\alpha^{3n}$ and $\beta^{3n}$ satisfy the recurrence $y_n=4y_{n-1}+y_{n-2}$. By linearity, so do the numbers $\frac{\alpha^{3n}-\beta^{3n}}{\sqrt{5}}$.

Comment: Note that using the same basic strategy, we can write down the recurrence satisfied by $\frac{\alpha^{kn}-\beta^{kn}}{\sqrt{5}}$. The coefficients that we painfully computed by hand, step by step, can be expressed simply in terms of Fibonacci numbers, and therefore so can the recurrence for the numbers $\frac{\alpha^{kn}-\beta^{kn}}{\sqrt{5}}$.

-
Nice! I think Newton-Girard might also yield a useful route here. – J. M. Dec 27 '11 at 5:11
I thought I would take an "unfancy" route through facts likely to be well-known. – André Nicolas Dec 27 '11 at 5:18
Here's the Newton-Girard route for completeness: one wants the characteristic polynomial $x^2-(\alpha^3+\beta^3)x+\alpha^3 \beta^3$ without knowing $\alpha$ or $\beta$, but knowing that $\alpha+\beta=1$ and $\alpha\beta=-1$ (Vieta). It is easily seen that $\alpha^3 \beta^3=-1$. Using Newton-Girard, we have the symmetric polynomial expansion $\alpha^3+\beta^3=(\alpha+\beta)^3-3(\alpha+\beta)(\alpha\beta)$, and thus $\alpha^3+\beta^3=(1)^3-3(1)(-1)=4$. The characteristic polynomial is thus $x^2-4x-1$. – J. M. Dec 27 '11 at 5:25
@J.M.: I think that the comment above should be made into an answer. – André Nicolas Dec 27 '11 at 5:29

By inspection $f(3n+3)=4f(3n)+f(3n-3)$, as you’ve already noticed. This is easily verified:

\begin{align*} f(3n+3)&=f(3n+2)+f(3n+1)\\ &=2f(3n+1)+f(3n)\\ &=3f(3n)+2f(3n-1)\\ &=3f(3n)+\big(f(3n)-f(3n-2)\big)+f(3n-1)\\ &=4f(3n)+f(3n-1)-f(3n-2)\\ &=4f(3n)+f(3n-3)\;. \end{align*}

However, I didn’t arrive at this systematically; it just ‘popped out’ as I worked at eliminating terms with unwanted indices.

Added: Here’s a systematic approach, but I worked it out after the fact.

The generating function for the Fibonacci numbers is $$g(x)=\frac{x}{1-x-x^2}=\frac1{\sqrt5}\left(\frac1{1-\varphi x}-\frac1{1-\hat\varphi x}\right)\;,$$ where $\varphi = \frac12(1+\sqrt5)$ and $\hat\varphi=\frac12(1-\sqrt5)$, so that $f(n)=\frac1{\sqrt5}(\varphi^n-\hat\varphi^n)$. Thus, $f(3n)=\frac1{\sqrt5}(\varphi^{3n}-\hat\varphi^{3n})$. Thus, we want

\begin{align*} h(x)&=\frac1{\sqrt5}\sum_{n\ge 0}(\varphi^{3n}-\hat\varphi^{3n})x^n\\ &=\frac1{\sqrt5}\left(\sum_{n\ge 0}\varphi^{3n}x^n-\sum_{n\ge 0}\hat\varphi^{3n}x^n\right)\\ &=\frac1{\sqrt5}\left(\frac1{1-\varphi^3 x}-\frac1{1-\hat\varphi^3 x}\right)\\ &=\frac1{\sqrt5}\cdot\frac{(\varphi^3-\hat\varphi^3)x}{1-(\varphi^3+\hat\varphi^3)x+(\varphi\hat\varphi)^3x^2}\;. \end{align*}

Now $\varphi+\hat\varphi=1$, $\varphi-\hat\varphi=\sqrt5$, $\varphi\hat\varphi=-1$, $\varphi^2=\varphi+1$, and $\hat\varphi^2=\hat\varphi+1$, so

\begin{align*} h(x)&=\frac1{\sqrt5}\cdot\frac{(\varphi^3-\hat\varphi^3)x}{1-(\varphi^3+\hat\varphi^3)x+(\varphi\hat\varphi)^3x^2}\\ &=\frac{(\varphi^2+\varphi\hat\varphi+\hat\varphi^2)x}{1-(\varphi^2-\varphi\hat\varphi)x-x^2}\\ &=\frac{(\varphi^2-1+\hat\varphi^2)x}{1-(\varphi^2+1+\hat\varphi^2)x-x^2}\\ &=\frac{(\varphi+\hat\varphi+1)x}{1-(\varphi+3+\hat\varphi)x-x^2}\\ &=\frac{2x}{1-4x-x^2}\;. \end{align*}

It follows that $(1-4x-x^2)h(x)=2x$ and hence that $h(x)=4xh(x)+x^2h(x)+2x$. Since the coefficient of $x^n$ in $h(x)$ is $f(3n)$, this tells me that

\begin{align*} \sum_{n\ge 0}f(3n)x^n&=h(x)=4xh(x)+x^2h(x)+2x\\ &=\sum_{n\ge 0}4f(3n)x^{n+1}+\sum_{n\ge 0}f(3n)x^{n+2}+2x\\ &=\sum_{n\ge 1}4f(3n-3)x^n+\sum_{n\ge 2}f(3n-6)x^n+2x\;, \end{align*}

which by equating coefficients immediately implies that $f(3n)=4f(3n-3)+f(3n-6)$ for $n\ge 2$. It also gets the initial conditions right: the constant term on the righthand side is $0$, and indeed $f(3\cdot 0)=0$, and the coefficient of $x$ is $4f(0)+2=2=f(3)$, as it should be.

-

Actually the "Magic Trick" or "Reverse Engineering" idea works nicely.

First, as André pointed

$$f_{3n}=\frac{\alpha^{3n}+\beta^{3n}}{\sqrt{5}} \,.$$

This means that if $(x-\alpha^{3})(x-\beta^3)=x^2-Ax-B$ then $f_{3n}$ is the recurrence satisfying

$$x_{n+2}=Ax_{n+1}+Bx_{n} \, x_{0}=f_0, x_1=f_{3} \,.$$

Thus,

$$f_6=Af_3+Bf_0$$ $$f_9=Af_6+Bf_3$$

Solve it and get $A,B$.

-

Let $S$ be the shift operator on sequences (as in Bill Dubuque's answer). Note that the Fibonacci sequence is killed by $S^2-S-1$. The Fibonacci sequence will then be killed by any "polynomial" multiple of $S^2-S-1$. To get a recurrence for every $k^{\rm{th}}$ term, all we need to do is find a multiple of $S^2-S-1$ that only involves powers of $S^k$.

First note that $S^2-S-1=(S-a)(S-b)$ where $a=\phi$ (the golden ratio) and $b=-1/\phi$. Consider the operator $(S^k-a^k)(S^k-b^k)=S^{2k}-(a^k+b^k)S^k+(ab)^k$. It is a polynomial multiple of $S^2-S-1$, so it kills the Fibonacci sequence. It only involves powers of $S^k$.

Recall that one formula for the $k^{\rm{th}}$ Lucas number is $L_k=a^k+b^k$, and note that $ab=-1$. Thus, we get that $S^{2k}-L_kS^k+(-1)^k$ kills the Fibonacci sequence.

Therefore, in summary, we get $$F_{n+2k}=L_kF_{n+k}-(-1)^kF_n\tag{1}$$ For example, $$F_{n+2}=F_{n+1}+F_n\tag{k=1}$$ $$F_{n+4}=3F_{n+2}-F_n\tag{k=2}$$ $$F_{n+6}=4F_{n+3}+F_n\tag{k=3}$$ $$F_{n+8}=7F_{n+4}-F_n\tag{k=4}$$ $$F_{n+10}=11F_{n+5}+F_n\tag{k=5}$$

-

We can write linear recurrence relations in terms of matrix multiplication like so:

$$F_{n+2} = \left[ \begin{array}{cc} 1 & 1 \end{array} \right] \left[ \begin{array}{cc} F_n \\ F_{n+1} \end{array} \right] = 1 \cdot F_n + 1 \cdot F_{n+1}.$$

Now if the sequence 0,2,8,34,144,610,2584,10946,... is called $G_n$, let's make the unjustified assumption that it is also a second order recurrence relation, then not only would we have

$$G_{n+2} = \left[ \begin{array}{cc} c_1 & c_2 \end{array} \right] \left[ \begin{array}{cc} G_n \\ G_{n+1} \end{array} \right]$$

for some unknowns $c_1$ and $c_2$, but also we can collect several instances of the above identity together into one e.g.

$$\left[ \begin{array}{cc} 34 & 144 \end{array} \right] = \left[ \begin{array}{cc} c_1 & c_2 \end{array} \right] \left[ \begin{array}{cc} 2 & 8 \\ 8 & 34 \end{array} \right]$$

and we can solve this using PARI/GP like so:

? [34,144]/[2,8;8,34]
% = [1, 4]


Therefore $G_{n+2} = 1 \cdot G_n + 4 \cdot G_{n+1}$.

About the assumption, it can be proved in general based on the ideas of characteristic function which you have seen in most of the answers. Given that, there is no need for any induction proofs or anything. Just computing the vector completes the proof of $G_{n+2} = 1 \cdot G_n + 4 \cdot G_{n+1}$.

-
Here's an interesting identity involving Lucas and Fibonacci numbers: $$\begin{pmatrix}\ell_k&(-1)^{k+1}\\1&0\end{pmatrix}=\begin{pmatrix}f_k&f_{k-1}\\0‌​&1\end{pmatrix}\cdot\begin{pmatrix}1&1\\1&0\end{pmatrix}^k \cdot\begin{pmatrix} f_k&f_{k-1}\\0&1\end{pmatrix}^{-1}$$ – J. M. Dec 28 '11 at 15:21

It is easy by operator algebra. Let the Shift, Triple $\mathbb C$-linear operators $\rm\ S\:n\: :=\: n+1,\ \ T\:n\: :=\: 3\:n\:$ act on fibonacci's numbers by $\rm\ S\:f(a\:n+b) = f(a\:(n+1)+b)\$ and $\rm\ T\:f(a\:n+b) = f(3\:a\:n+b)\:.$ Below I show a general method that works for any Lucas sequence $\rm\:f(n)\:$ that involves only simple high-school polynomial arithmetic (albeit noncommutative). Namely, one employs a commutation rule $\rm\: TS\:\to\: (a\ S + b)\ T\$ to shift $\rm\:T\:$ past powers of $\rm\:S\:,\:$ in order to transmute the known recurrence $\rm\ q(S)\ f(n)\: =\: 0\$ into $\rm\ \bar{q}(S)\:T\:f(n)\:=\:0\:,\$ the sought recurrence for $\rm\ T\:f(n)\: =\: f(3\:n)\:.\:$

We know $\rm\ q(S)\ f(n) := (S^2 - S - 1)\ f(n)\: =\: f(n+2) - f(n+1) - f(n)\: =\: 0\:.\:$ We seek an analogous recurrence $\rm\ \bar{q}(S)\ T\: f(n)\ =\ 0\$ for $\rm\ T\:f(n) = f(3\:n)\:,\:$ and some polynomial $\rm\:\bar{q}(S)\:.\:$ Since clearly we have that $\rm\ T\:q(S)\ f(n)\: =\: 0\:,\:$ it suffices to somehow transmute this equation by shifting $\rm\:T\:$ past $\rm\:q(S)\:$ to yield $\rm\:\bar{q}(S)\:T\:f(n)\:=\:0\:.\:$ To do this, it suffices to find some commutation identity $\rm T\:S\: =\: r(S)\: T\$ to enable us to shift $\rm\:T\:$ past $\rm\:S$'s in each monomial $\rm\ S^{\:i}\: f(n)\: =\: f(n+i)\:$ from $\rm\:q(S)\:.\:$ The sought commutation identity arises very simply: iterate the recurrence for $\rm\:f(n)\:$ so to rewrite

$\rm\ ST\ f(n)\ =\ f(3\:n+3)\$ as a linear combination of $\rm\ f(3\:n+1) = TS\ f(n)\:,\:$ $\rm\ f(3\:n) = T\ f(n)\:,\:$ viz.

$\rm\ \ \ ST\ f(n+i)\ =\ f(3n+3+i)\ =\ f(3n+2+i) + f(3n+1+i)\ =\ 2\ f(3n+1+i) + f(3n+i)$

$\rm\ \ \ \phantom{ST\ f(n+i)}\ =\ (2\:TS+T)\ f(n+i)\quad$ for all $\rm\:i\in \mathbb Z\:$

$\rm\ 2\:TS\ f(n+i)\ =\ (S-1)\:T\ f(n+i)\:,\$ i.e. $\rm\ 2\:TS\ =\ (S-1)\:T\:,\$ the sought commutation identity.

Thus $\rm\qquad\quad\:\ 0\ =\ 4\: T\: (S^2 - S - 1)\ f(n)\$

$\rm\qquad\qquad\qquad\quad\ \ =\ (2\:(2TS)S - 2\:(2TS) - 4\:T)\ f(n)$

$\rm\qquad\qquad\qquad\quad\ \ =\ ((S-1)\:2TS - 2\:(S-1)\:T - 4\:T)\ f(n)$

$\rm\qquad\qquad\qquad\quad\ \ =\ ((S-1)^2 - 2\:(S-1)\: - 4)\ T\: f(n)$

$\rm\qquad\qquad\qquad\quad\ \ =\ (S^2 - 4\ S - 1)\ T\: f(n)$

$\quad$ i.e. $\rm\qquad\quad\: 0\ =\ f(3(n+2)) - 4\ f(3(n+1)) - f(3\:n)\qquad$ QED

NOTE $\$ Precisely the same method works for any Lucas sequence $\rm\:f(n)\:,\:$ i.e. any solution of $\rm\ 0\ =\ (S^2 + b\ S + c)\ f(n)\ =\ f(n+2) + b\ f(n+1) + c\ f(n)\$ for constants $\rm\:b,\:c\:,\:$ and for any multiplication operator $\rm\:T\:n = k\ n\:$ for $\rm\:k\in \mathbb N\:.\:$ As above, we obtain a commutation identity by iterating the recurrence (or powering its companion matrix), in order to rewrite

$\rm\ ST\ f(n)\ =\ f(k\:n+k)\$ as a $\rm\:\mathbb C$-linear combination of $\rm\ f(kn+1) = TS\ f(n)\$ and $\rm\ f(kn) = T\ f(n)\:$

say $\rm\ \ ST\ f(n)\ =\ f(k\:n+k)\ =\ a\ f(k\:n+1) + d\ f(k\:n)\ =\ (a\ TS + d\ T)\ f(n)\ \$ for some $\rm\:a,d\in \mathbb C$

$\rm\:\Rightarrow\ a\ TS\ f(n) =\ (S-d)\ T\ f(n)\ \Rightarrow\ a\ TS\ =\ (S-d)\ T\$ on $\rm\ S^{\:i}\: f(n)\$ as above.

Again, this enables us to transmute the recurrence for $\rm\:f(n)\:$ into one for $\rm\:T\:f(n) = f(k\:n)\:$ by simply commuting $\rm\:T\:$ past all $\rm\:S^i\:$ terms. Hence the solution involves only simple polynomial arithmetic (but, alas, the notation obscures the utter simplicity of the method).

-