Simple closed functional form for summed recurrence relation

Question

I'm struggling to obtain a simple closed form for a summed recurrence relation. I have an overall form

$y=A\left(n-\sum_i^n\frac{e^{-x_i}}{B}\right)$

where $x_{i+1}=kx_i+m$ with $A,B,m >1$ and $0<k<1$

I don't even know where to begin getting something in the form

$y=f(x,A,B,m,k)$

so any help would be appreciated.

Answer 1

You can solve the recurrence for the $x_i$. Divide the recurrence by $k^{i + 1}$ to get:

$$ \frac{x_{i + 1}}{k^{i + 1}} - \frac{x_i}{k^i} = \frac{m}{k^{i + 1}} $$

If you sum over $i$, the left hand side telescopes nicely:

$$ \frac{x_r}{k^r} - x_0 = \sum_{0 \le i \le r - 1} m k^{-i - 1} = \frac{m}{k^r} \frac{k^r - 1}{k - 1} $$

Thus:

$$ x_r = x_0 k^r + m \frac{k^r - 1}{k - 1} $$

In case $k = 1$, the solution is just $x_r = x_0 + r m$.

You can plug this into your sum, but unless $k = 1$ there is probably no way to reduce this to a closed form.

Knowing more about the parameters you could use the above to derive a decent approximation for your sum (e.g. if $k > 1$, only the first few terms will matter in the sum defining $y$)