Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Check this technique or generating function technique. – Mhenni Benghorbal Apr 12 '14 at 0:52
Another technique. – Mhenni Benghorbal Apr 12 '14 at 0:58
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|cite|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|cite|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|cite|improve this answer

Your Answer


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.