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

  • $\begingroup$ What have you done so far? $\endgroup$ – Semiclassical Jul 16 '14 at 20:49
  • $\begingroup$ Why do you think there exists a closed formula? $\endgroup$ – Crostul Jul 16 '14 at 20:51
  • $\begingroup$ So far, I don't understand how I can find the closed formula. $\endgroup$ – hlapointe Jul 16 '14 at 20:52
  • 1
    $\begingroup$ 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.) $\endgroup$ – Semiclassical Jul 16 '14 at 20:54
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Jul 16 '14 at 20:55

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

  • $\begingroup$ You must have committed a mistake somewhere. According to WolframAlpha, this is the solution. $\endgroup$ – Deathkamp Drone Jul 16 '14 at 22:14
  • $\begingroup$ I decided very quickly and missed the constant value. This new version is now corrected. $\endgroup$ – Mathsource Jul 16 '14 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$.

  • $\begingroup$ Are you sure there's not an easy way because I really don't understand your approach. $\endgroup$ – hlapointe Jul 16 '14 at 21:07
  • $\begingroup$ 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? $\endgroup$ – Joel Jul 16 '14 at 21:08
  • 1
    $\begingroup$ 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. $\endgroup$ – Semiclassical Jul 16 '14 at 21:09
  • 2
    $\begingroup$ @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. $\endgroup$ – David Holden Jul 16 '14 at 21:10
  • 1
    $\begingroup$ Ok. I wil try to studie this approach. $\endgroup$ – hlapointe Jul 16 '14 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}$$

  • $\begingroup$ Not really. I barely understand your manipulations. Can you show me how to apply the characteristic equation? $\endgroup$ – hlapointe Jul 16 '14 at 21:30
  • $\begingroup$ 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. $\endgroup$ – Deathkamp Drone Jul 16 '14 at 21:39
  • $\begingroup$ 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? $\endgroup$ – Semiclassical Jul 16 '14 at 21:47
  • $\begingroup$ 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). $\endgroup$ – Deathkamp Drone Jul 16 '14 at 22:08

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.