1
$\begingroup$

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.

Appreciate your help!

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

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ That's elegant. Thanks a lot, this was very helpful! $\endgroup$
    – Anton2107
    Jun 19 at 12:01
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you! I understand it now! $\endgroup$
    – Anton2107
    Jun 19 at 12:02
0
$\begingroup$

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

$\endgroup$

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.