recurrence relation where $c_n = c_{n-1} + 2c_{n-2}$

117 Views Asked by At

A sequence $(c_n)$ is defined recursively as follows: $c_0 = 1, c_1 = 1, $ and $c_n = c_{n-1} + 2c_{n-2}$ for $n\geq 2$. We use $[x^n]g(x)$ to denote the coefficient of $x^n$ of the polynomial $g(x).$ Show that $c_{2n} = [x^{2n}] \dfrac{1}2\left(\dfrac{1}{1-x-2x^2}+\dfrac{1}{1+x-2x^2}\right)$ and that $\sum_{n\geq 0} c_{2n}x^n = \dfrac{1-2x}{1-5x+4x^2}.$ From this, one can deduce that $c_{2n} = 5c_{2n-2} - 4c_{2n-4}.$ Obtain a similar equation for $c_{2n}, c_{2n-4}$ and $c_{2n-8}.$

I know that $\dfrac{1}2\left(\dfrac{1}{1-x-2x^2}+\dfrac{1}{1+x-2x^2}\right) = \dfrac{1-2x^2}{1-5x^2+4x^4}$ and so if I show that $c_{2n} = [x^{2n}] \dfrac{1-2x^2}{1-5x^2+4x^4},$ I can replace $x^2$ with $x$ and get that $\sum_{n\geq 0} c_{2n}x^n = \dfrac{1-2x}{1-5x+4x^2}$. But I'm not sure how to show that $c_{2n} = [x^{2n}] \dfrac{1-2x^2}{1-5x^2+4x^4}.$ I don't think I'll need to compute the exact coefficient and it does not seem useful to manipulate the recurrence equation by substituting $n$ with $2n$. I tried showing that $(1-5x^2+4x^4) \sum_{n\geq 0} c_{2n} x^{2n} = 1-2x^2.$ Matching coefficients results in $c_0+(c_2-5c_0)x^2 + \sum_{n\geq 0} (c_{2n}-5c_{2n-2}-2c_{2n-4})x^{2n} = 1-2x^2,$ but it seems I'd need to prove something like $c_{2n}-5c_{2n-2}-2c_{2n-4}.$ I think figuring out how to come up with $\dfrac{1-2x}{1-5x+4x^2}$ should help me obtain a similar equation relating $c_{2n}, c_{2n-4}, c_{2n-8}$

2

There are 2 best solutions below

0
On BEST ANSWER

Your attempt to equate coefficients in

$$(1-5x^2+4x^4)\sum_{n\ge 0}c_{2n}x^{2n}=1-2x^2$$

will work if you do it correctly. When you multiply out the lefthand side you should get

$$c_0+(c_2-5c_0)x^2+\sum_{n\ge 2}(c_{2n}-5c_{2n-2}+4c_{2n-4})x^{2n}=1-2x^2\,,$$

and you know that $c_0=1$ and $c_2=3$, so this reduces to

$$\sum_{n\ge 2}(c_{2n}-5c_{2n-2}+4c_{2n-4})x^{2n}=0\,.$$

This means that $c_{2n}-5c_{2n-2}+4c_{2n-4}\equiv 0$ for $n\ge 2$ and gives you the recurrence $c_{2n}=5c_{2n-2}-4c_{2n-4}$. And from that you can work backwards to get

$$\sum_{n\ge 0}c_{2n}x^{2n}=\frac{1-2x^2}{1-5x^2+4x^4}$$

and the rest. There is probably some perfectly reasonable way to get their first expression for $c_{2n}$ and work forwards, but I’m not seeing it at the moment. Unfortunately, that means that what I did above may not adapt easily to let you solve the last part of the problem. I can, however, offer an alternative approach.

It’s easy enough simply to solve the recurrence and get an explicit formula for $c_n$. We have the recurrence $c_n=c_{n-1}+2c_{n-2}+[n=0]$, where the last term is an Iverson bracket added to make the recurrence valid for all $n$ if we assume that $c_n=0$ for $n<0$. Multiplying through by $x$ and summing over $n$ we have

$$g(x)=xg(x)+2x^2g(x)+1$$

and hence

$$g(x)=\frac1{1-x-2x^2}=\frac1{(1+x)(1-2x)}\,.$$

Decomposing this into partial fractions, we get

$$\begin{align*} g(x)&=\frac13\left(\frac2{1-2x}+\frac1{1+x}\right)\\ &=\frac13\left(2\sum_{n\ge 0}2^nx^n+\sum_{n\ge 0}(-1)^nx^n\right)\\ &=\frac13\sum_{n\ge 0}\left(2^{n+1}+(-1)^n\right)x^n\,, \end{align*}$$

so that $c_{2n}=\frac{2^{2n+1}+1}3\,.$ It is now easy to verify that

$$\begin{align*} 5c_{2n-2}-4c_{2n-4}&=\frac{5\cdot 2^{2n-1}+5-4\cdot 2^{2n-3}-4}3\\ &=\frac{20\cdot2^{2n-3}-4\cdot 2^{2n-3}+1}3\\ &=\frac{2^{2n+1}+1}3\\ &=c_{2n}\,. \end{align*}$$

If you use the closed form to write out $c_{2n},c_{2n-4}$, and $c_{2n-8}$ and tinker a bit along the lines of that last calculation of mine, you should be able to come up with the coefficients $\alpha$ and $\beta$ for the recurrence $c_{2n}=\alpha c_{2n-4}+\beta c_{2n-8}$.

1
On

Using generating functions, I obtained the expression for $G(z) = \sum_n c_n z^n$: $$ G(z) = \frac{c_0(1-z)+c_1z}{(1+z)(1-2z)} $$ Now you need to expand the expression with partial fractions, you will obtain on RHS two expressions of the form $$ G(z) = \lambda_1\sum_{z=0}^{\infty}(-1)^kz^k + \lambda_1\sum_{z=0}^{\infty}(-s_1)^kz^k $$ By taking the coefficients for the term $z^n$ you will get your closed-form expression. Here you will need to find the constants $\lambda_1, \lambda_2$ using partial fractions, and $s_1$ by using Generalized binomial coefficient for $\frac{1}{1-2z}$. Can you handle from here?

EDIT: In the partial fraction step it's better to group $c_0 + (c_1-c_0)z$