2

I've been trying to solve the following equation intuitively (I only know the method if there are minuses in the equation - $a_{n-1}, a_{n-2}...$).

$$a_{n+2}=4a_{n+1}-4a_{n}$$ $$a_{0}=3$$ $$a_{1}=8$$

$$ \begin{align} A(x)&=\sum\limits_{n>=0}a_{n}x^{n} \\ &= \sum\limits_{n>=0}(a_{n+1}-\frac{1}{4}a_{n+2})x^{n} \\ &= \sum\limits_{n>=0}(a_{n+1})x^{n}-\frac{1}{4}\sum\limits_{n>=0}(a_{n+2})x^{n} \\ &= \sum\limits_{n>=1}(a_{n})x^{n+1}-\frac{1}{4}\sum\limits_{n>=2}(a_{n})x^{n+2} \\ &= \frac{1}{x}\sum\limits_{n>=1}(a_{n})x^{n}-\frac{1}{4x^{2}}\sum\limits_{n>=2}(a_{n})x^{n} \\ &= \frac{1}{x}[\sum\limits_{n>=0}(a_{n})x^{n} - 3]-\frac{1}{4x^{2}}[\sum\limits_{n>=0}(a_{n})x^{n} - 3 - 8x] \\ &= \frac{1}{x}[A(x) - 3]-\frac{1}{4x^{2}}[A(x) - 3 - 8x] \end{align} $$

So I get

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

Is this correct? I'm asking because the answer to this question according to the source I got it from is $x^{2}-4x+4$ as the denominator...

Ben Grossmann
  • 225,327
khernik
  • 1,369
  • So which one is the equation? Is $A(x)$ part of it? Your first line is a forward scheme that appears to diverge... – Doctor Dan Aug 15 '13 at 16:27
  • If you want to reduce the problem to one you know, substitute $n$ with $n-2$. You might also be interested in a linear algebra approach? – Evan Aug 15 '13 at 16:30
  • So this is the same as $a_{n}=4a_{n-1}-4a_{n-2}$? – khernik Aug 15 '13 at 16:38
  • Note that $a_n = (n+3) \cdot 2^n$ – Will Jagy Aug 15 '13 at 16:45
  • @khernik yes. Also, your 4th equality sign has the issue. When you do such index reshuffling, just sanity check by plugging in a sample index value. i.e. the first term of the sum on the third line is $a_1 x^0$ whereas the first term of the sum on the fourth is $a_2 x^2$. Same goes for later lines when you start pulling out $x$'s. Each operation is introducing a mistake :) – Evan Aug 16 '13 at 00:29

2 Answers2

1

Not sure where you went wrong, so I'll start from scratch with a different method:

Let $A(x)=\sum_{n=0}^\infty a_nx^n$. Note that $a_n$ satisfies $a_{n+2}-4a_{n+1}+4a_n=0$. Let $p(x)=1-4x+4x^2$. We then define $$ B(x) = \sum_{n=0}^\infty b_nx^n=p(x)A(x) $$ Note that for $n\geq2$, we have $b_n=a_{n+2}-4a_{n+1}+4a_n=0$. So, we simply have $$ p(x)A(x) = b_0+b_1 x $$ Thus, $$ A(x) = \frac{b_0+b_1 x}{1-4x+4x^2}=\frac{a_0+(a_1-4a_0) x}{1-4x+4x^2}=\frac{3-4x}{1-4x+4x^2} $$ It seems you have the right answer, and that your source has a typo.

Ben Grossmann
  • 225,327
1

Just another approach for verification.

Assume $$ a_{n+2}=4a_{n+1}-4a_{n} $$ Then $$ \begin{align} f(x)&=\sum_{k=0}^\infty a_kx^k\\ xf(x)&=\sum_{k=1}^\infty a_{k-1}x^k\\ x^2f(x)&=\sum_{k=2}^\infty a_{k-2}x^k\\ \end{align} $$ Then we get $$ \begin{align} f(x)(1-4x+4x^2)&=a_0+a_1x-4a_0x+\sum_{k=2}^\infty(a_k-4a_{k-1}+4a_{k-2})x^k\\ &=a_0+(a_1-4a_0)x\\[18pt] f(x)&=\frac{a_0+(a_1-4a_0)x}{1-4x+4x^2}\\ &=\frac{3-4x}{1-4x+4x^2} \end{align} $$

robjohn
  • 345,667