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.

How might one solve the recurrence

$x_{n+1} + x_n + 2^n = 0$

given the necessary initial conditions ($x_0$)?

Possible ideas I have in mind:

1) Generating functions

2) Discrete Laplace Transforms

Any other possible techniques?

share|improve this question
    
Check this technique or generating function technique. –  Mhenni Benghorbal Apr 12 at 0:52
    
Another technique. –  Mhenni Benghorbal Apr 12 at 0:58

3 Answers 3

up vote 6 down vote accepted

Divide by $2^{n}$, we then get $$\dfrac{x_{n+1}}{2^n} + \dfrac{x_n}{2^n} + 1 = 0$$ Let $y_n = \dfrac{x_n}{2^n}$. This gives us $$2y_{n+1} + y_n + 1 = 0 \implies 2(y_{n+1}+1/3) + (y_n+1/3) = 0$$ Define $z_n = y_n + 1/3$ to get $$2z_{n+1} = -z_n \implies z_{n+1} = \left(-\dfrac12\right)^{n+1} z_0$$ Obtain $x_n$ from this. Move your mouse over the gray area for the complete solution.

$$y_n = -\dfrac13 + \left(-\dfrac12\right)^{n}(y_0+1/3) \implies x_n = -\dfrac{2^n}3 + (-1)^n\left(\dfrac{x_0}{2^n}+\dfrac13\right)$$$$x_n = \left(-\dfrac12\right)^nx_0 + \dfrac{(-1)^n-2^n}3$$

share|improve this answer

Generating functions: Define $X(z) = \sum_{n \ge 0} x_n z^n$, multiply by $z^n$ and sum over $n \ge 0$ to get: $$ \frac{X(z) - x_0}{z} + X(z) + \frac{1}{1 - 2 z} = 0 $$ Thus, written as partial fractions: $$ X(z) = \frac{1 + 3 x_0}{3 (1 + z)} - \frac{1}{3 (1 - 2 z)} $$ From here the coefficients can be read off directly: $$ x_n = \frac{1 + 3 x_0}{3} \cdot (-1)^n - \frac{2^n}{3} $$

share|improve this answer

The general solution of the homogeneous equation $x_{n+1}=-x_n$ is $A(-1)^n$. Now look for a particular solution of the inhomogeneous equation. "Guess" that there is a solution of the shape $k2^n$. We get $k2^{n+1}+k2^n=-2^n$, giving $k=-\frac{1}{3}$. thus the general solution is $-\frac{2^n}{3}+(-1)^n A$.

share|improve this answer

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.