Solving a recurrence based on the solution to another.

Question

I have a solution to a recurrence $g(n)=f(n) + g(n-1)$, and I'd like to solve the recurrence $h(n) = \alpha[f(n) + h(n-1)]$. I guessed the solution was $h(n) = \alpha^ng(n)$, but it turns out this holds iff $\alpha = 1$ or $f \equiv 0$.

Answer 1

The solution to $g(n)=f(n)+g(n-1)$ (treating $g$ as unknown and $f$ as known) is $g(n)=f(n)+f(n-1)+\cdots+f(1)+g(0)$.

The solution to $h(n)=\alpha(f(n)+h(n-1))$ is $h(n)=\alpha f(n)+\alpha^2f(n-1)+\cdots+\alpha^nf(1)+\alpha^nh(0)$.

So it seems that you are asking, if you know $f(n)+f(n-1)+\cdots+f(1)$, can you work out $\alpha f(n)+\alpha^2f(n-1)+\cdots+\alpha^nf(1)$.

And the answer is, surely not.

Answer 2

Suppose we know $s(n) = \sum_{k=1}^n f(k)$, and we want to know $r(n, x) = \sum_{k=1}^n x^{n+1-k}f(k)$.

$f(n) = s(n)-s(n-1)$, so

$\begin{align} r(n, x) &= \sum_{k=1}^n x^{n+1-k}f(k) \\ &= \sum_{k=1}^n x^{n+1-k} (s(k)-s(k-1)) \\ &= \sum_{k=1}^n x^{n+1-k} s(k)-\sum_{k=1}^n x^{n+1-k}s(k-1) \\ &= \sum_{k=1}^n x^{n+1-k} s(k)-\sum_{k=0}^{n-1} x^{n-k}s(k) \\ &= x s(n) - x^n s(0) + \sum_{k=1}^{n-1} s(k)(x^{n+1-k} -x^{n-k}) \\ &= x s(n) + (x-1)\sum_{k=1}^{n-1} x^{n-k}s(k) \\ \end{align} $

Not sure whether this helps or not, but it is a formula.