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?
Best Answer
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.