Finding a non-recursive formula for a recursively defined sequence So I have a recursive definition for a sequence, which goes as follows:
$$s_0 = 1$$
$$s_1 = 2$$
$$s_n = 2s_{n-1} - s_{n-2} + 1$$
and I have to prove the following proposition: The $n$th term of the sequence defined above is $s_n = \frac{n(n+1)}{2} + 1$.
To prove this, I started it off by induction. The base case is for $n = 0$ and its true since the non-recursive and recursive results match. I assumed the following hypothesis to be true for some $n = k$: that the $n$th term of the sequence is $s_k = \frac{k(k+1)}{2} + 1$. Then, in the induction step, we need to show that $s_{k + 1} = \frac{(k+1)(k+2)}{2} + 1$. 
Using the recursive definition of the sequence, we have that $s_{k+1} = 2s_k - s_{k-1} + 1$, so we can use the hypothesis to replace $s_k$ and $s_{k-1}$ by their non-recursive formulas:
$$ s_{k+1} = 2 (\frac{k(k + 1)}{2} + 1) - (\frac{(k-1)k}{2} + 1)  + 1$$
After simplifying i get
$$ s_{k+1} = \frac{k(k+3)}{2} + 2 $$
which is clearly wrong. Can someone point out what I'm doing wrong and where I can go with this?
EDIT: The answer I have given is correct, except that we need to simplify further to get the form we want:
$$ \frac{k(k+3)}{2} + 2 = \frac{k^2 + 3k + 4}{2}$$
after expansion and common denominators, and then this is clearly equal to
$$ \frac{(k+1)(k+2)}{2} + 1 = \frac{k^2 + 3k + 2}{2} + 1 = \frac{k^2 + 3k + 4}{2} $$
 A: Your work is fine. 
$${s_{k + 1}} = \frac{{k(k + 3)}}{2} + 2 = \frac{{k(k + 3) + 2}}{2} + 1 = \frac{{{k^2} + 3k + 2}}{2} + 1 = \frac{{\left( {k + 1} \right)\left( {k + 2} \right)}}{2} + 1$$
As GitGud has pointed out, you should assume that the formulas for $s_k$ and $s_{k-1}$ hold true, since you need them both for your recurrence.
A: At the end of this answer is a brief description of inverting finite difference operators. In the case here
$$
\begin{align}
\Delta^2s_k
&=s_n-2s_{n-1}+s_{n-2}\\
&=1
\end{align}
$$
Is a second order finite difference operator. Inverting the operator by summing twice, we get that the solution is of the form
$$
s_n=\frac12n^2+c_1n+c_0
$$
We can compute the constants by plugging in known values:
$$
\frac12\cdot0^2+c_i\cdot0+c_0=s_0=1\\
\frac12\cdot1^2+c_i\cdot1+c_0=s_1=2
$$
Thus, $c_0=1$ and $c_1=\frac12$. Therefore,
$$
\begin{align}
s_n
&=\frac12n^2+\frac12n+1\\
&=\frac{n(n+1)}{2}+1
\end{align}
$$

The only problem in your solution is that you left out the $+1$
$$
\begin{align}
s_{k+1}
&=2\left(\frac{k(k+1)}{2}+1\right)-\left(\frac{(k-1)k}{2}+1\right)\color{#C00000}{+1}\\
&=(k^2+k+2)-\frac12(k^2-k+2)+1\\
&=\frac{k^2+3k+4}{2}\\
&=\frac{(k+1)(k+2)}{2}+1
\end{align}
$$
However, since the answer you got was $\frac{k(k+3)}{2}+2$, perhaps the omission of the $+1$ was simply a typo. In that case, you got the right answer since
$$
\frac{k(k+3)}{2}+2=\frac{(k+1)(k+2)}{2}+1
$$
