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?

  • $\begingroup$ 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)$ $\endgroup$
    – Will Jagy
    Nov 5, 2017 at 1:28
  • $\begingroup$ @WilJagy , thanks I fixed the typo. How would one start working something out? Getting the exact solution? $\endgroup$
    – jman
    Nov 5, 2017 at 1:32
  • $\begingroup$ It appears you do not get much unless your $b = 1.$ $\endgroup$
    – Will Jagy
    Nov 5, 2017 at 2:21

2 Answers 2


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.