# Fibonacci-like doubling identities for recurrences of the form $G(k) = a \, G(k-1) + b \,G(k-2) + c$?

The Fibonacci numbers have the doubling identities:

\begin{align} F(2 k) &= F(k) \left[ 2 F(k+1) - F(k) \right] \\ F(2k+1) &= F(k+1)^2+F(k)^2 . \end{align}

I was wondering if there are similar identities for a general recurrence of the form:

\begin{equation} G(k) = a \, G(k-1) + b \,G(k-2) + c \end{equation}

How would one go about finding such identities and/or the conditions on $a,b,c,$ and boundary conditions which would yield such identities?

• f you take $c=0$ you should be able to work out something. You should have written $G(k+2) = a G(k+1) + b G(k)$ Nov 5, 2017 at 1:28
• @WilJagy , thanks I fixed the typo. How would one start working something out? Getting the exact solution?
– jman
Nov 5, 2017 at 1:32
• It appears you do not get much unless your $b = 1.$ Nov 5, 2017 at 2:21

Let's take a slighly-more-specific (no free-floating constant), yet slightly-more-general (the leading term has a coefficient) recursion:

$$a G(k+2) = b G(k+1) + c G(k) \tag{\star}$$

I've shifted the placement of your $a$, $b$, $c$ coefficients, although ultimately this won't matter: I'll express the final formulas using terms from the sequence.

(Caveat: I'll be ignoring situations in which various denominators vanish. Rectifying the formulas for those cases is left as an exercise to the reader.)

Using a standard recursion-solving technique, we can write a closed formula for $G(k)$ in terms of the roots of the quadratic equation $a g^2 - b g - c = 0$: $$G(k) = p g_{+}^k + m g_{-}^k \qquad\text{where}\qquad g_{\pm} := \frac{1}{2a}\left(b\pm d\right)\quad\text{and}\quad d := \sqrt{b^2+4ac} \tag{1}$$

We can solve for $p$ and $m$ in terms of the initial terms of the sequence: \begin{align}g_0 &:= G(0) = p+m \\ g_1 &:= G(1) = p g_{+} + m g_{-}\end{align} \tag{2} This system yields $$p = -\frac{g_1 - g_0 g_{-}}{g_{-} - g_{+}} = \frac{a}{d}\left(g_1 - g_0 g_{-}\right) \qquad\qquad m =\frac{ g_1 - g_0 g_{+}}{ g_{-} - g_{+} } = -\frac{a}{d}\left( g_1 - g_0 g_{+}\right) \tag{3}$$ whereupon $$G(k) = \frac{a}{d}\left(\; (g_1 - g_0 g_{-} ) g_{+}^k - (g_1 - g_0 g_{+})g_{-}^k\;\right) \tag{4}$$ But then also \begin{align} G(k+1) &= \frac{a}{d}\left(\; (g_1 - g_0 g_{-} ) g_{+}^{k+1} - (g_1 - g_0 g_{+})g_{-}^{k+1}\;\right) \\ &= \frac{a}{d}\left(\; (g_1 - g_0 g_{-} ) g_{+} g_{+}^{k} - (g_1 - g_0 g_{+}) g_{-} g_{-}^{k}\;\right) \tag{5} \end{align}

These equations allow us to solve for $g_{\pm}^k$ in terms of $g_k := G(k)$ and $g_{k+1} := G(k+1)$: \begin{align} g_{+}^k &= -\frac{d ( g_{k+1} - g_k g_{-})}{ a (g_{-} - g_{+})(g_1 - g_0 g_{-})} = \frac{g_{k+1} - g_k g_{-}}{g_1 - g_0 g_{-}} \tag{6a}\\ g_{-}^k &= -\frac{d (g_{k+1} - g_k g_{+})}{ a (g_{-} - g_{+}) (g_1 - g_0 g_{+})} = \frac{g_{k+1} - g_k g_{+}}{g_1 - g_0 g_{+}} \tag{6b} \end{align}

Therefore, \begin{align} G(2k) &= \frac{a}{d}\left(\; (g_1 - g_0 g_{-} ) g_{+}^{2k} - (g_1 - g_0 g_{+})g_{-}^{2k}\;\right) \tag{7a}\\[4pt] &= \frac{a}{d}\left(\; (g_1 - g_0 g_{-} ) \left(g_{+}^{k}\right)^2 - (g_1 - g_0 g_{+})\left(g_{-}^{k}\right)^2\;\right) \tag{7b}\\[4pt] &= \frac{a}{d}\left(\; \frac{(g_{k+1} - g_k g_{-})^2}{g_1 - g_0 g_{-}} - \frac{(g_{k+1} - g_k g_{+})^2}{g_1 - g_0 g_{+}}\;\right) \tag{7c}\\[4pt] &= \frac{a}{d} \frac{(g_{-}-g_{+})( g_{k}^2 ( g_1 (g_{-}+ g_{+}) - g_0 g_{-} g_{+} ) -2 g_1 g_k g_{k+1} + g_0 g_{k+1}^2 )}{(g_1^2 - g_0 (g_1 (g_{-}+g_{+}) - g_0 g_{-}g_{+}))} \tag{7d} \\[4pt] &= \frac{a}{d} \frac{(g_{-}-g_{+})( g_{k}^2 ( g_1 (b/a) - g_0 (-c/a) ) -2 g_1 g_k g_{k+1} + g_0 g_{k+1}^2 )}{(g_1^2 - g_0 (g_1 (b/a) - g_0 (-c/a) ))} \tag{7e} \\[4pt] &= -\frac{ g_{k}^2 ( b g_1 + c g_0 ) -2 a g_1 g_k g_{k+1} + a g_0 g_{k+1}^2 }{(a g_1^2 - g_0 (b g_1 + c g_0))} \tag{7f}\\[4pt] &= \frac{ g_2 g_{k}^2 - 2 g_1 g_k g_{k+1} + g_0 g_{k+1}^2}{g_0 g_2 - g_1^2} \tag{7g} \end{align} (Note that, writing the numerator as $g_2 g_k g_k - 2 g_1 g_k g_{k+1} + g_0 g_{k+1}g_{k+1}$, the sum-of-subscripts in each term is $2k+2$; and in the denominator, we have $2$. Thus, the "net sum-of-subscripts" is $2k$.) Also, \begin{align} G(2k+1) &= \frac{a}{d}\left(\; (g_1 - g_0 g_{-} ) g_{+}\left(g_{+}^{k}\right)^2 - (g_1 - g_0 g_{+})g_{-}\left(g_{-}^{k}\right)^2\;\right) \tag{8a} \\[4pt] &= \cdots \tag{\cdots}\\[4pt] &=-\frac{c}{a} \frac{ g_1 g_k^2 - 2 g_0 g_k g_{k+1} + g_{-1} g_{k+1}^2}{g_0 g_2 - g_1^2} \tag{8z} \end{align} provided that $g_{-1}$ is defined by $a g_1 = b g_0 + c g_{-1}$. But, if we're going to use $g_{-1}$, we might as well combine its defining relation with $a g_2 = b g_1 + c g_0$ to solve for $a$ and $c$ in terms of $b$ and $g$s: $$a = -b\frac{g_1g_{-1}-g_0^2}{g_0g_1-g_2g_{-1}} \qquad c = b\frac{g_0g_2-g_1^2}{g_0 g_1-g_2g_{-1}} \qquad\to\qquad -\frac{c}{a} = \frac{g_0g_2-g_1^2}{g_1g_{-1}-g_0^2} \tag{9}$$ Thus, we can write $$G(2k+1) = \frac{ g_1 g_k^2 - 2 g_0 g_k g_{k+1} + g_{-1} g_{k+1}^2}{g_1g_{-1}-g_0^2} \tag{10}$$

(Here, the "net sum-of-subscripts" is $2k+1$.)

Note: For the Fibonacci numbers, $a=b=c=g_1=g_2=g_{-1}=1$, $g_0=0$, so that formulas $(7g)$ and $(10)$ reduce to the identities given in the question.

After much algebra I was able to find:

\begin{equation} G(2n) + \frac{2 (a-1) (-b)^n}{a^2+2 b} =\left[ \frac{(a-1) a^3+(4 a-3) a b+2 b^2}{a (a+b-1) \left(a^2+2 b\right)} \right] G(n+1)^2 - \left[ \frac{b^3 (a+2 b)}{a (a+b-1) \left(a^2+2 b\right)} \right] G(n-1)^2 \end{equation}

If the boundary conditions are, $G(1) = G(2) = 1$ and $c=0$. A formula for \$G(2n+1) I'm sure would look equally as monstrous.