Finding associated Difference equation.

Question

Assume I have some arbitrary difference equation, which should equate to $2^{n+3} - 1$. A quick way to solve this is to use the annihilator method, but I have not fully understanded how to use this. My main problem lies within finding the difference equation where the before mentioned $2^{n+3} -1 $ would be the solution. I know from the solutions that $y(n+2) -3y(n+1) + 2y(n)$ is the difference equation solved by $2^{n+3} -1 $, but how do I (quickly) find this?

Answer 1

This is an interesting problem. Consider a generalized Fibonacci sequence

$$ f_n=af_{n-1}+bf_{n-2} $$

As I've pointed out previously here, for example, the characteristic roots are given by

$$ \alpha, \beta = \frac{a \pm\sqrt{a^2 + 4b}}{2}. $$

Since you provide $\alpha=2, \beta=1$ we can determine that $a=3$ from $\alpha+\beta=3$ and $b=-2$ from $\alpha-\beta=1$, i.e., $\sqrt{a^2+4b}=1$ or $b=(1-a^2)/4$.

To complete the solution, we need the general solution to the recurrence above. It can be expressed follows,

$$ f_n=\frac{(f_1-f_0\beta)\alpha^n - (f_1-f_0\alpha)\beta^n}{\alpha-\beta} $$

With the information you provide, $f_0=2^3-1=7, f_1=2^4-1=15$ and we can the readily show that, indeed

$$ f_n=2^{n+3}-1 $$

for

$$ f_n=3f_{n-1}-2f_{n-2},\quad f_0=7,f_1=15 $$

Answer 2

Noting that the sequence also satisfies the first-order inhomogeneous difference equation $f_{n+1} = 2 f_n + 1$, if we want to find a homogeneous equation then we can start by writing

$$f_{n+2} = a f_{n+1} + b f_n$$

and then do some substitutions and expansions. That will give us:

$$\begin{eqnarray}& 2^{n + 5} - 1 & = & a\left(2^{n + 4} - 1\right) + b\left(2^{n + 3} - 1\right) \\ & 32 \cdot 2^n - 1 & = & a\left(16 \cdot 2^n - 1\right) + b\left(8 \cdot 2^n - 1\right) \\ & & = & \left(16 a + 8 b\right) 2^n - \left(a + b\right) \\ \implies & 16 a + 8 b & = & 32 \\ \mbox{and} & a + b & = & 1 \end{eqnarray}$$

and you can solve the last two equations quite easily to get $a = 3, b = -2$.