I want to solve following difference equation:

$a_i = \frac13a_{i+1} + \frac23a_{i-1}$, where $a_0=0$ and $a_{i+2} = 1$

My approach: Substituting $i=1$ in the equation,
$3a_1 = a_2 + 2a_0$
$a_2 = 3a_1$
Similarly substituting $i = 2, 3 ...$
$a_3 = 7a_1$
$a_4 = 15a_1$

$a_i = (2^i - 1)a_1$

I am not sure how to get rid of $a_1$ to get the final answer of $\frac{(2^i - 1)}{(2^{2+i} - 1)}$

  • $\begingroup$ Hint: write it as $\,a_{n+1} = 3 a_n - 2a_{n-1} \iff a_{n+1} -a_{n} = 2( a_n - a_{n-1})\,$, so $\,a_{n+1} -a_{n}\,$ is a geometric progression with common ratio $\,2\,$. Find $\,a_{n+1} -a_{n}\,$, then find $\,a_n\,$ by telescoping, then use the boundary conditions to determine the constants. $\endgroup$ – dxiv Mar 1 '18 at 0:02
  • $\begingroup$ Thank @dxiv . GP gives $a_{i+1} -a_i = 2^ia_1$. Or, $a_{i+2} -a_{i+1} = 2^{i+1}a_1$. Or, $a_i = 1-2^ia_1$. This is somehow different from what I got above. I have already applied both boundary conditions. $\endgroup$ – Gerry Mar 1 '18 at 20:54
  • $\begingroup$ GP gives ... No, that should rather be $\,a_{n+1}-a_{n}=2^n(a_1-a_0)\,$. Then, by telescoping, $a_{n+1}-a_{0}=(2^n+2^{n-1}+\ldots+2^1 + 1)(a_1-a_0)=\ldots$ $\endgroup$ – dxiv Mar 2 '18 at 0:22

The standard method to solve recurrence equations is to set as trial solution

$$a_i=x^i \implies x^i = \frac13x^{i+1} + \frac23 x^{i-1}\implies x =\frac13 x^2+\frac23\implies x^2-3x+2=0$$

then find $x_1$ and $x_2$ then the general solution is

$$x_i = ax_1^i+bx_2^i$$

with $a$ and $b$ determined by initial conditions.
Solving, $x_1=1, x_2=2$
Substituting, $x_i = a + 2^ib$
Using boundary conditions and solving through, $a = \frac{-1}{(2^{i+2}-1)}$ and $b = \frac{1}{(2^{i+2}-1)}$
Plugging back these into general solution equation and rearranging: $a_i = \frac{(2^{i}-1)}{(2^{i+2}-1)}$

| cite | improve this answer | |
  • $\begingroup$ Well done! then my hint was useful! $\endgroup$ – user Mar 1 '18 at 21:06
  • $\begingroup$ Thanks gimusi. This is very helpful $\endgroup$ – Gerry Mar 1 '18 at 22:05
  • $\begingroup$ @Gerry I'm very happy for that., Thanks, Bye. If you want a good reference take also a look here youtube.com/watch?v=PNrqCdslGi4 $\endgroup$ – user Mar 1 '18 at 22:08

If you proceed this way, $a_1$ is an unknown, to be solved for by substituting in the boundary condition at the other endpoint and solving for $a_1$. (This is actually a fairly common trick, for instance it is also used to derive the invariant distribution of a birth-death process by writing all the $\pi_i$'s in terms of $\pi_0$ and then choosing $\pi_0$ based on the normalization requirement.)

| cite | improve this answer | |

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.