3
$\begingroup$

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)$.

$\endgroup$
2
$\begingroup$

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)$$

$\endgroup$
  • $\begingroup$ It didn't occur to me to introduce a new variable $s$, I was too stuck on looking at $b^k$. $\endgroup$ – orlp Jul 3 '17 at 9:35
1
$\begingroup$

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.