# Find expression of $c_n$, where $c_n = a_n + b_n$

Given the recurrence relation $$a_{n+2} = 3a_{n+1} + 6a_n$$ and $$b_{n+2} = b_{n+1} + b_n$$ I am supposed to find an expression of the recurrence relation for $$c_n := a_n + b_n$$. I tried to find some form of linear dependence to obtain a recurrence relation for $$c_n$$ but this did not let me finish.

• Do you mean that you want the recurrence fomula of $c_n$? Jun 19 at 9:58
• Yes, I'm struggling calculating a nice formula for $c_n$ Jun 19 at 10:49
• Have you learnt eigenvalue and diagonalisation? Jun 19 at 11:04
• Yes, we did. Does this help? Jun 19 at 11:06
• Should it be $b_0$ in the second recurrence? Jun 19 at 11:11

If I define the generating functions

$$f(x) = \sum_{n=0}^\infty a_n x^n$$

$$g(x) = \sum_{n=0}^\infty b_n x^n$$

then

\begin{align*} (6x^2 + 3x - 1) f(x) &= \sum_{n=0}^\infty (6 a_n x^{n+2} + 3 a_n x^{n+1} - a_n x^n)\\ &= -a_0 + (3 a_0 - a_1) x + \sum_{n=2}^\infty (6 a_{n-2} + 3 a_{n-1} - a_n) x^n \\ &= -a_0 + (3 a_0 - a_1) x \end{align*}

$$f(x) = \frac{A + Bx}{6x^2 + 3x - 1}$$

\begin{align*} (x^2+x-1) g(x) &= \sum_{n=0}^\infty (b_n x^{n+2} + b_n x^{n+1} - b_n x^n) \\ &= -b_0 + (b_0-b_1)x + \sum_{n=2}^\infty(b_{n-2}+b_{n-1}-b_n)x^n \\ &= -b_0 + (b_0-b_1)x \end{align*}

$$g(x) = \frac{C + Dx}{x^2+x-1}$$

The generating function for $$c_n$$ is $$f+g$$:

$$\sum_{n=0}^\infty c_n x^n = \sum_{n=0}^\infty (a_n+b_n) x^n = f(x) + g(x)$$

And that sum is a fraction of polynomials, where the numerator $$P(x)$$ has degree at most $$3$$, but its exact form doesn't matter for this purpose:

$$f(x) + g(x) = \frac{P(x)}{(6x^2+3x-1)(x^2+x-1)} = \frac{P(x)}{6x^4 + 9x^3 - 4x^2 - 4x + 1}$$

\begin{align*} P(x) &= (6x^4+9x^3-4x^2-4x+1)(f(x)+g(x)) \\ &= \sum_{n=0}^\infty (6c_n x^{n+4} + 9c_n x^{n+3} - 4c_n x^{n+2} - 4c_n x^{n+1} + c_n x^n) \\ &= Q(x) + \sum_{n=4}^\infty (6c_{n-4} + 9c_{n-3} -4c_{n-2} - 4c_{n-1} + c_n) x^n \end{align*}

where $$Q(x)$$ is another polynomial of degree at most $$3$$ of "left over" terms. The equality forces $$P(x) = Q(x)$$ and all coefficients in the infinite sum must be zero.

So shifting the index, we get the recurrence relation for all $$n \geq 0$$:

$$c_{n+4} = 4c_{n+3} + 4c_{n+2} - 9c_{n+1} - 6c_n$$

• That's elegant. Thanks a lot, this was very helpful! Jun 19 at 12:01

If $$a_{n+2}=3a_{n+1}+6a_n$$ iff $$a_n=d_1r_1^n+d_2r_2^n$$, where $$r_1,r_2$$ are the roots of $$x^2-3x-6=0$$, and $$b_{n+2}=a_{n+1}+a_n$$ iff $$b_n=d_3r_3^n+d_4r_4^n$$, where $$r_3,r_4$$ are the roots of $$x^2-x-1=0$$, and $$d_1,d_2,d_3,d_4$$ are arbitrary constants.

Hence, $$c_n=a_n+b_n=d_1r_1^n+d_2r_2^n+d_3r_3^n+d_4r_4^n$$ which holds iff $$c_{n+4}=4c_{n+3}+4c_{n+2}-9c_{n+1}-6c_n$$ since $$r_1,r_2,r_3,r_4$$ are the roots of $$(x^2-3x-6)(x^2-x-1)=x^4-4x^3-4x^2+9x+6=0.$$

Note. The following result is not hard to prove:

Lemma. If the roots of $$p(x)=x^k-s_{1}x^{k-1}-s_{2}x^{k-2}-\cdots-s_k$$ are the distinct complex numbers $$r_1,\ldots,r_k$$ then $$a_{n+k}=s_{1}a_{n+k-1}+s_{2}a_{n+k-2}+\cdots+s_ka_n$$ iff $$a_n=d_1r_1^n+\cdots+d_kr_k^n$$, for some constants $$d_1,\ldots,d_k$$.

• Thank you! I understand it now! Jun 19 at 12:02

Using that $$\,a_{n+2} - 3a_{n+1} - 6a_n = 0\,$$ and $$\,b_{n+2} = b_{n+1} + b_n\,$$:

\require{cancel} \begin{align} c_{n+2}-3c_{n+1}-6c_n &= \cancel{(a_{n+2}-3a_{n+1}-6a_n)} + (b_{n+2}-3b_{n+1}-6b_n) \\ &= -2b_{n+1} - 5 b_n \end{align}

Then, using that $$\,b_{n+2} - b_{n+1} - b_n = 0\,$$:

\begin{align} (c_{n+4} - 3c_{n+3}-6c_{n+2}&) - (c_{n+3}-3c_{n+2}-6c_{n+1}) - (c_{n+2}-3c_{n+1}-6c_n) \\ &=\; -2\cancel{(b_{n+3}-b_{n+2}-b_{n+1})} - 5\bcancel{(b_{n+2}-b_{n+1}-b_{n})} \\ &= 0 \end{align} $$\iff c_{n+4} - 4c_{n+3}-4c_{n+2}+9 c_{n+1}+ 6 c_n = 0$$