Question about recurrences algorithm design and anaylsis

Question

I have a question about recurrences. The following problem is:

$a_k = 0$ if $k = 0$, $a_k = a_{k−1} + 3k + 1$ if $k > 0$

I need to: write out the first six terms of recurrences, make a guess for explicit formula an, and prove using induction.

Any help is appreciated, as I am having trouble even approaching the problem.

Answer 1

Hint:

If $P(k)$ is a polynomial in $k$ of degree $p$, then $Q(k):=P(k)-P(k-1)$ is a polynomial in $k$ of degree $p-1$. Knowing $Q$, this helps you find $P$ by indeterminate coefficients.

Answer 2

Just go at it:

$\begin{align*} a_0 &= 0 \\ a_1 &= a_0 + 3 \cdot 1 + 1 \\ &= 3 \cdot 1 + 1 \\ a_2 &= a_1 + 3 \cdot 2 + 1 \\ &= 3 \cdot 1 + 1 + 3 \cdot 2 + 1 \\ &= 3 \cdot (1 + 2) + 1 + 1 \\ a_3 &= a_2 + 3 \cdot 3 + 1 \\ &= 3 \cdot (1 + 2) + 2 + 3 \cdot 3 + 1 \\ &= 3 \cdot (1 + 2 + 3) + 2 + 1 \\ &= 3 \cdot (1 + 2 + 3) + 3 \end{align*}$

What does this look like, up to here? Three down, three to go...

Answer 3

A general way to solve recurrences is generating functions. Define:

$\begin{align*} A(z) &= \sum_{n \ge 0} a_n z^n \end{align*}$

Shift your recurrence, multiply by $z^n$, sum over $n \ge 0$, recognize the resulting sums:

$\begin{align*} \sum_{k \ge 0} a_{k + 1} z^k &= \sum_{k \ge 0} a_k z^k + 3 \sum_{k \ge 0} (k + 1) z^k + \sum_{k \ge 0} z^k \\ \frac{A(z) - a_0}{z} &= A(z) + 3 \frac{z}{(1 - z)^2} + \frac{4}{1 - z} \end{align*}$

Here we used:

$\begin{align*} \frac{1}{1 - z} &= \sum_{k \ge 0} z^k \\ \sum_{k \ge 0} k z^k &= z \frac{d}{d z} \sum_{k \ge 0} z^k \\ &= z \frac{d}{d z} \frac{1}{1 - z} \\ &= \frac{z}{(1 - z)^2} \end{align*}$

Solve for $A(z)$, as partial fractions:

$\begin{align*} A(z) &= \frac{z (4 - z)}{(1 - z)^3} \\ &= \frac{3}{(1 - z)^3} - \frac{2}{(1 - z)^2} - \frac{1}{1 - z} \end{align*}$

To extract coefficients, remember:

$\begin{align*} (1 + u)^{-m} &= \sum_{k \ge 0} \binom{-m}{k} u^k \\ &= \sum_{k \ge 0} (-1)^k \binom{k + m - 1}{m - 1} u^k \end{align*}$

Thus: $\begin{align*} [z^k] A(z) &= 3 (-1)^k \binom{k + 3 - 1}{3 - 1} (-1)^k - 2 (-1)^k \binom{k + 2 - 1}{2 - 1} (-1)^k - (-1)^k \binom{k + 1 - 1}{1 - 1} (-1)^k \\ &= 3 \binom{k + 2}{2} - 2 \binom{k + 1}{1} - \binom{k}{0} \\ &= 3 \frac{(k + 2) (k + 1)}{2} - 5 \frac{k + 1}{1} + 2 \\ &= \frac{k (3 k + 5)}{2} \end{align*}$

Answer 4

It is easy to see that a recurrence of the form $a_k=a_{k-1}+f(k)$ with $a_0=0,$ implying $a_1=f(1),a_2=f(1)+f(2),\cdots$ has the general solution $$a_k=\sum_{i=1}^k f(i).$$

Hence for your equation,

$$a_k=\sum_{i=1}^k (3k+1)=3\sum_{i=1}^kk+\sum_{i=1}^k1=3T_k+k$$ where $T_k$ denotes a triangular number.