Set up difference equation for the following recurrence.

Question

I have the following recurrence:

$t=0: 0$
$t=1: 0$
$t=2: 1$
$t=3: \beta+\alpha$
$t=4: (\beta+\alpha)\alpha+\beta^2$
$t=5: ((\beta+\alpha)\alpha+\beta^2)\alpha+\beta^3$
...

I was hoping to do something like:

$x_{t+1}=x_{t}f_{t}+g_{t}$ with

$f_{t}=\alpha$ and $g_{t}=\beta^{t-1}$

But it does not fit with $t=0$ and $t=1$ both has to be $0$.

Is there anyway to set up this difference equation without using indicator functions or piecewiese functions for $g_{t}$?

Answer 1

If you expand your terms you'll find the recurrence has a fairly simple closed form (hint: multiply by $\alpha-\beta$), for which the case $t=0$ doesn't match the formula.

Answer 2

I dont't know if this is what you are looking for, but ...

Use $x_{t+1}=(x_{t}f_{t}+g_{t})h(t)$ where $h(t) = [\dfrac{t(t-1)}{t(t-1) - 1/2}]$.

We have: $ h(0)=h(1)=0 $ and $1<=\dfrac{t(t-1)}{t(t-1) - 1/2}<2$ $ \forall t>1$ so $h(t)=1 $ $\forall t>1$

Answer 3

Call your value $a_t$, after $t = 3$ it is $a_{t + 1} = \alpha a_t + \beta^{t - 2}$, with $a_3 = \alpha + \beta$. Set up a generating function $A(z) = \sum_{t \ge 0} a_{t + 3} z^t$, multiply the recurrence by $z^t$ and sum over $t \ge 0$:

$\begin{align} \sum_{t \ge 0} a_{t + 4} z^t &= \alpha \sum_{t \ge 0} a_{t + 3} z^t + \sum_{t \ge 0} \beta^{t + 1} z^t \\ \frac{A(z) - a_3}{z} &= \alpha A(z) + \frac{\beta}{1 - \beta z} \end{align}$

Plugging in $a_3 = \alpha + \beta$ and solving for $A(z)$ gives, unless $\alpha = \beta$:

$\begin{align} A(z) &= \frac{(\alpha + \beta) - \beta(\alpha + \beta - 1) z} {(1 - \alpha z) (1 - \beta z)} \\ &= \frac{\beta^2 - \beta - \alpha^2}{\beta - \alpha} \cdot \frac{1}{1 - \alpha z} + \frac{\beta}{\beta - \alpha} \cdot \frac{1}{1 - \beta z} \end{align}$

and your solution is:

$$ a_{t + 3} = \frac{\beta^2 - \beta - \alpha^2}{\beta - \alpha} \cdot \alpha^t + \frac{\beta^{t + 1}}{\beta - \alpha} $$

If $\alpha = \beta$:

$\begin{align} A(z) &= \frac{2 \alpha - \alpha(2 \alpha - 1) z}{(1 - \alpha z)^2} \\ &= \frac{2 \alpha - 1}{1 - \alpha z} + \frac{1}{(1 - \alpha z)^2} \end{align}$

from which you have directly:

$$ a_{t + 3} = (2 \alpha - 1) \cdot \alpha^t + (n + 1) \cdot \alpha^t = (n + 2 \alpha) \cdot \alpha^t $$

Earlier values don't follow the pattern.