Closed form for solution of $f(n) = an + b\sum\limits_{k=0}^{n-1}f(k)$

Question

Is there a closed form for the general recurrence

$$f(n) = an + b\sum_{k=0}^{n-1}f(k)$$

with constants $a, b$?

After playing around with it for a bit I conjectured $\displaystyle f(n) = a\frac{(b+1)^n - 1}{b}$, but I have no idea how to prove it. I have a vague feeling generating functions are related, as we are looking at the coefficients of $b^k$ for a certain $f(n)$.

Answer 1

The most usual approach based on generating functions works. To wit, note that $f(0)=0$, $f(1)=a$, and that $$F(s)=\sum_{n=0}^\infty f(n)s^n$$ solves $$F(s)=\sum_{n=0}^\infty ans^n+b\sum_{n=0}^\infty \sum_{k=0}^{n-1}f(k)s^n=as\sum_{n=0}^\infty ns^{n-1}+b\sum_{k=0}^\infty f(k)\sum_{n=k+1}^{\infty}s^n$$ that is, $$F(s)=\frac{as}{(1-s)^2}+b\sum_{k=0}^\infty f(k)\frac{s^{k+1}}{1-s}=\frac{as}{(1-s)^2}+\frac{bs}{1-s}F(s)$$ which implies that $$F(s)=\frac{as}{(1-s)(1-(b+1)s)}=\frac{a}b\left(\frac1{1-(b+1)s}-\frac1{1-s}\right)$$ that is, $$F(s)=\frac{a}b\left(\sum_{n=0}^\infty(b+1)^ns^n-\sum_{n=0}^\infty s^n\right)$$ which indeed yields, for every $n$, $$f(n)=\frac{a}b\left((b+1)^n-1\right)$$

Answer 2

Alternative hint:  let $\,g_n=\sum_{k=0}^{n}f(k)\,$, then $\,f(n)=g_n-g_{n-1}\,$ and the recurrence rewrites as:

$$g_n - g_{n-1} = an + bg_{n-1} \;\;\iff\;\;g_n = (b+1)\,g_{n-1} + an \quad\;\;\text{with}\;\;g_0=f(0)=0$$

The latter is a standard linear recurrence with the solution:

$$g_n=\frac{a}{b^2}\big((b+1)^{n+1}-(b+1)-bn\big)$$

Then:

$$\require{cancel} \begin{align} f(n)=g_n-g_{n-1} & =\frac{a}{b^2}\big((b+1)^{n+1}-\cancel{(b+1)}-\bcancel{bn}\big) - \frac{a}{b^2}\big((b+1)^{n}-\cancel{(b+1)}-b(\bcancel{n}-1)\big) \\ &= \frac{a}{b^2}\big((b+1)^n(b+\cancel{1}-\cancel{1})-b\big) \\ &= \frac{a}{b}\big((b+1)^n-1\big) \\ \end{align} $$