Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What's the closed formula of this recurrence relation? $$a_n = a_{n-1}+2a_{n-2}+2^n \text{ with } a_0=1, a_1=2 $$

share|improve this question
    
What have you done so far? –  Semiclassical Jul 16 at 20:49
    
Why do you think there exists a closed formula? –  Crostul Jul 16 at 20:51
    
So far, I don't understand how I can find the closed formula. –  hlapointe Jul 16 at 20:52
1  
If you know how to do the first part of that, you should say so in the question so that readers can gauge your understanding. (Plus, writing out the first few terms usually helps to clarify the solution.) –  Semiclassical Jul 16 at 20:54
    
Do you know how to use characterisstic equation, in this case $x^2-x-2=0$? We don't really need it in this case, guess and verify might work. –  André Nicolas Jul 16 at 20:55

3 Answers 3

up vote 4 down vote accepted

This is nonhomogeneneous difference equations. First solve the homogeneous equation $$ a_n - a_{n-1} - 2a_{n-2} = 0 \quad (1) $$ Let $a_n = r^n$, so that $a_{n-1} = r^{n-1}$ and $r_{n-2} = r^{n-2} = 0$. Replacing in (1), we have $$ r^n - r^{n-1} - 2r^{n-2} = 0 \quad r^2 - r - 2 = 0 \quad \Rightarrow \ r_1 = -1, \ r_2 = 2 $$ $$ a_{nh} = C_1(-1)^n + C_22^n $$ Particular solution: Let $a_{np} = a_n = An2^n$. The presence of n is due to the fact that $2$ is a root of the equation (1). So, $a_{n-1} = A(n-1)2^{n-1}$ and $a_{n-2} = A(n-2)2^{n-2}$. Substituting in the given equation, we have $$ An2^n + (An - A)2^{n-1} - 2A(n-2)2^{n-2} = 2^n \quad \Rightarrow \quad A = \frac{2}{3} $$ Thus, $a_n = a_{nh} + a_{np} = C_1(-1)^n + C_22^n + \frac{2n2^n}{3}$. But, $a_0 = a(0) = 1$ and $a_1 = a(1) = 2$. We have the system $$ \begin{cases} 1 = a_0 = C_1 + C_2\\ 2 = a_1 = -C_1 + C_2 + \frac{8}{3} \end{cases} \quad \Rightarrow \quad C_1 = 8/9, \quad C_2 = 1/9 $$ Thus, $$ a_n = \frac{8(-1)^n}{9} + \frac{1}{9}2^n + \frac{2n2^n}{3} $$

share|improve this answer
    
You must have committed a mistake somewhere. According to WolframAlpha, this is the solution. –  Deathkamp Drone Jul 16 at 22:14
    
I decided very quickly and missed the constant value. This new version is now corrected. –  MathFacts Jul 16 at 22:53

A generating function approach would make this straightforward:

$$G(x) = \sum_{n=0}^\infty a_n x^n = 1+2x+\sum_{n=2}^\infty a_n x^n$$ $$=1+2x+\sum_{n=2}^\infty (a_{n-1} + 2a_{n-2} + 2^n)x^n$$ $$=1+2x+\sum_{n=1}^\infty a_n x^{n+1} + 2 \sum_{n=0}^\infty a_n x^{n+2} + \sum_{n=2}^\infty 2^n x^n$$ $$=1+2x+x(G(x)-1)+2x^2G(x)+\frac{2^2x^2}{1-2x}$$

Thus $$G(x)(1-x-2x^2) = 1+x+\frac{2^2x^2}{1-2x}$$ and $$G(x) = \frac{1+x}{1-x-2x^2} + \frac{2^2x^2}{(1-2x)(1-x-2x^2)} = \frac{1+x}{(1+x)(1-2x)} + \frac{2^2x^2}{(1-2x)(1+x)(1-2x)}$$ $$= \frac{1}{(1-2x)} + \frac{2^2x^2}{(1-2x)^2(1+x)}$$

Now you can use partial fractions, and then expand in terms of geometric series to find the taylor coefficients of $G(x)$ which are the terms $a_n$.

share|improve this answer
    
Are you sure there's not an easy way because I really don't understand your approach. –  hlapointe Jul 16 at 21:07
    
This is a standard approach for linear recurrence relations. The idea is that $G(x)$ stores the information of the $a_n$'s in its taylor coefficients. Then you try to use the recurrence to rewrite $G(x)$ into an easier form (in this case a rational function). What is your background? –  Joel Jul 16 at 21:08
1  
It's the standard form if you really want to do well at it, anyways. An intro discrete math course might gloss that, I guess. –  Semiclassical Jul 16 at 21:09
2  
@hlapointe Joel's is a very good solution, you should check out generating functions. the underlying idea is not difficult to grasp, and for motivation, this problem is a good illustration of the power of the technique. –  David Holden Jul 16 at 21:10
1  
Ok. I wil try to studie this approach. –  hlapointe Jul 16 at 21:11

The best course of action for simple inhomogeneous recurrences is to make use of a smart "change of variables" (read: substitute with another recurrence relation) to turn it into a homogeneous recurrence. A nice observation here is to notice that $2^n$ is itself a recurrence relation, namely:

$$y_n=2y_{n-1},\,\,(y_0=1)$$ Let's use this to our advantage:

$$\begin{align} a_n=a_{n-1}+2a_{n-2}+2^n &\Leftrightarrow 2^n=a_n-a_{n-1}-2a_{n-2} \\ &\Leftrightarrow 2\cdot2^{n-1}=a_n-a_{n-1}-2a_{n-2} \\ &\Leftrightarrow 2\cdot (a_{n-1}-a_{n-2}-2a_{n-3})=a_n-a_{n-1}-2a_{n-2} \\ &\Leftrightarrow a_n-3a_{n-1}+4a_{n-3}=0 \end{align}$$

Bam, homogeneous recurrence. Can apply the characteristic equation and finish it by yourself?

Edit: The characteristic equation for the last recurrence is $x^3-3x+4=0$, whose roots are $2,2$ and $-1$. It is well-known then, that given these roots, the solution is of the form: $$a_n=(An+B)2^n+C(-1)^n$$

For some constants $A,B,C$. To find out what the constants are, we plug in values of $n$ for which the value of $a_n$ is known. The values of $a_0,a_1$ were given, but we need three to solve a linear system with three variables. We can easily calculate $a_2$: $$a_2=a_1+2a_0+2^2=8$$

Now we solve the system:

$$\begin{cases} (A\cdot0+B)2^0+C(-1)^0=1 \\ (A\cdot1+B)2^1+C(-1)^1=2 \Rightarrow \\ (A\cdot2+B)2^2+C(-1)^2=8 \end{cases}$$

$$\Rightarrow \begin{cases} B+C=1 \\ 2(A+B)-C=2 \\ 4(2A+B)+C=8 \end{cases}$$

Solving this will yield $A=\frac{2}{3}$,$B=\frac{5}{9}$ and $C=\frac{4}{9}$. Therefore, the closed form is: $$a_n=\frac{(6n+5)2^n+4(-1)^n}{9}$$

share|improve this answer
    
Not really. I barely understand your manipulations. Can you show me how to apply the characteristic equation? –  hlapointe Jul 16 at 21:30
    
Sorry, I commited an arithmetic mistake. It should be fixed now. The characteristic equation for the last recurrence is $x^3-3x+4=0$, whose roots are $-1$ and $2$ (with double multiplicity). You can use it to solve the last recurrence. –  Deathkamp Drone Jul 16 at 21:39
    
One point that's well-worth mulling: how is the characteristic equation in this case related to the one you had from the original relation? –  Semiclassical Jul 16 at 21:47
    
Do you understand it now? The only manipulation I did was to isolate $2^n$ and see that $2^n=a_n-a_{n-1}-2a_{n-2}$. With this we can infer that $2^{n-1}=a_{n-1}-a_{n-2}-2a_{n-3}$, and so we substitute it and the $2^n$ is gone. That was the whole motivation after all: I was assuming you were comfortable with solving linear homogeneous recurrences (since you said you knew about the characteristic polynomial). –  Deathkamp Drone Jul 16 at 22:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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