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} $$
$\endgroup$ 22 Answers
$\begingroup$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.
$\endgroup$ 4 $\begingroup$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 $$
$\endgroup$
