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} $$
Best Answer
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.