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

Question

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"?

Answer 1

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{eqnarray} 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{eqnarray}$$

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

Answer 2

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$)

Like André, I shall also start with Binet:

$$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)}$.

Answer 3

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}}$.

Answer 4

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.

Answer 5

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$.

Answer 6

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} $$

Answer 7

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}$.

Answer 8

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).