Concrete Mathematics: Sums and Recurrences question

Question

In the book by Knuth, Graham, Patashnik : section 2.2: Sums and Recurrences it is given $$S_0 = a_0;$$ $$S_n = S_{n-1}+a_n,$$ General Form (2.7): $$R_0 = \alpha$$ $$R_n = R_{n-1} + \beta + \gamma n$$ In general the solution can be written in the form (2.8): $$R_n = A(n) \alpha + B(n) \beta + C(n) \gamma$$

Here is where I get confused:

Setting $R_n = n^2$ implies $\alpha=0,\beta=-1,\gamma=2$; hence: $$2C(n) - B(n) = n^2$$ and we have $C(n)=\frac{n^2+n}{2}$

I understand why $\alpha=0,\beta=-1,\gamma=2$ and why $2C(n) - B(n) = n^2$, but have trouble understanding how $C(n)=\frac{n^2+n}{2}$ is derived, which implies $B(n)=n$

Answer 1

\begin{align} &R_n =R_{n-1}+\beta+\gamma n \\ &R_{n-1}=R_{n-2}+\beta+\gamma (n-1) \\ &R_{n-2}=R_{n-3}+\beta+\gamma (n-2)\\ &\text{so on ..}\\&R_2=R_1+ \beta+2 \gamma\\ &R_1=\alpha +\beta+\gamma \end{align}

Now add all those equations, you can see that all $R_i$ are cancelled and we are left with -

$$R_n=n \beta +(1+2+3 \ldots n) \gamma=n \beta+\left(\frac{n^2+n}{2}\right) \gamma$$

Answer 2

If my understanding is correct then there is another way to derive $(n^2 + n)/2$ using our earlier obtained repertoire item $B(n) = n$.

So using the $R_n=n^2$ implication that $\alpha=0$, $\beta=-1$, and $\gamma=2$ we have (being verbose)

$$ \begin{align} n^2 &= A(n)\cdot0 + B(n)\cdot-1 + C(n)\cdot2 \\ n^2 &= 0 -B(n) + 2C(n) \\ n^2 &= 2C(n) -B(n) \end{align} $$

At this point we know $B(n)=n$ (from previous repertoire step for $B(n)$) so sub that in and rearrange to get the result

$$ \begin{align} n^2 &= 2C(n) - n \\ n^2 + n &= 2C(n) \\ \frac{n^2 + n}{2} &= C(n) \end{align} $$