First Order Non-Homogeneous Linear Recurrence for Summation

Question

I've been studying Linear Recurrences in the non-homogeneous case, but have gotten stuck with the following problem: Find a closed form for $s_n=\sum_{i=1}^n i$. I know the answer is $n(n+1)/2$ by other methods, but I cannot seem to get the right answer using the recursion methods.

Here's my attempt: The sequence satisfies the non-homogeneous recurrence $s_n-s_{n-1}=n$. So consider the associated homogeneous recurrence $\overline{s_n}-\overline{s_{n-1}}=0$. This obviously has solution $\overline{s_n}=C_1$ for some constant $C_1$.

Next we find try to find a particular solution. Since the non-homogeneous part is linear, we should guess $s^{(p)}_n = A n+B$ for constants $A$ and $B$. But then, substituting back into the original recurrence, gives $(An+B)-(A(n-1)+B) = A$. It is impossible for the constant $A$ to equal the variable $n$. And so I'm stuck.

I'm guessing that I should have tried a particular solution that was a quadratic, but in all the books I've looked at, the particular solution has degree equal to the non-homogeneous part.

So what I am doing wrong?

Answer 1

I found the answer/explanation in "Discrete and Combinatorial Mathematics" by Grimaldi. He first gives the general rule:

[I]f a summand $f_1(n)$ of $f(n)$ is a constant multiple of a solution of the associated homogeneous relation... we multiply the particular solution $a_{n_1}^{(p)}$ corresponding to $f_1(n)$ by the smallest power of $n$, say $n^s$, for which no summand of $n^s f_1(n)$ is a solution of the associated homogeneous relation.

He then goes on to demonstrate this in the case $a_{n+1}-a_n=n$:

We might think that the particular solution is $A_1n+A_0$ for constants $A_0$ and $A_1$. But here the associated homogeneous relation is $a_{n+1}=a_n$. ... Therefore, the summand $A_0$ is a solution of the associated homogeneous relation. Consequently, the [rule] above tells us that we must multiply $A_1n+A_0$ by the smallest power of $n$ for which we no longer have any constant summand. This is accomplished by multiplying $A_1n+A_0$ by $n^1$, and so we find here that $$a_n^{(p)}=A_1n^2+A_0n.$$

Answer 2

The thing is, you want the difference $s_n-s_{n-1}$ to be $n$, a polynomial of degree one.

Something you should, do, or will know is that the first difference of a polynomial of degree $m$ is a polynomial of degree $m-1$.

Therefore, to make the difference of a polynomial to have degree $1$, the polynomial has to be of degree $2$.

Once you see this, the rest should be relatively routine.