2
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.