Induction Proof for Sequences

Question

Given a sequence $s_k=s_{k-1}+6k$, where $s_0=7$.

Question: First, find the closed formula for the $n$-th component of this sequence by hand and then prove that your formula is correct

My attempt: I found the first couple of terms of the sequence to be $s_0=7$, $s_1=13$, $s_2=25$, $s_3=43$, $s_4=67$ and $s_5=97$.

I found the formula for the $n$-th term to be $s_n=3n^2+3n+7$.

Proof: Base case $s_0=7$ therefore $7=3\cdot(0)^2+3\cdot(0)+7$ so the formula works for the $s_0$ element.

I'm not sure how to proceed from here but I believe the proof should be a proof by Strong Induction. Any help will be greatly appreciated.

Answer 1

It seems to me that induction is not needed here. Fix $k\in\Bbb N.$ A direct computation shows that $s_k-s_{k-1}=6k$ and $s_0=7.$ However, there is another problem: both induction, and my method show that if $s_k=3k^2+3k+7$, then $s_{k}=s_{k-1}+6k$. In fact, whe should prove the converse: if $s_{k}=s_{k-1}+6k$ and $s_0=7$, then $s_k=3k^2+3k+7$. I will look for some reasoning going in this direction.

Let $s_0=7$ and $s_{k}=s_{k-1}+6k.$ Define $t_k=s_k-3k^2-3k-7.$ Then $t_0=0$. It is easy to prove (by direct computation) that $t_k=t_{k-1}$, so $(t_k)$ is a constant (in fact, zero) sequence. Then $s_k=3k^2+3k+7.$

Answer 2

You just apply the recurrence to your induction hypothesis.

If $s_n=3n^2+3n+7 $, then, since $s_k=s_{k-1}+6k $,

$\begin{array}\\ s_{n+1} &=s_n+6(n+1)\\ &=3n^2+3n+7+6(n+1)\\ &=3n^2+9n+13\\ \end{array} $

If your hypothesis is true, then

$\begin{array}\\ s_{n+1} &=3(n+1)^2+3(n+1)+7\\ &=3(n^2+2n+1)+3(n+1)+7\\ &=3n^2+6n+3+3n+3+7\\ &=3n^2+9n+13\\ \end{array} $

This matches the result from the induction step, so the induction hypothesis is proved.

Answer 3

FYI, here is a way to determine what the closed formula is without having to determine it by hand. This is an extension of the answer given by szw1710. The given sequence is

$$s_k=s_{k-1}+6k \tag{1}\label{eq1}$$

Summing both sides of \eqref{eq1} from $1$ to $n$ gives that

$\sum_{k=1}^{n}s_k = \sum_{k=1}^{n}s_{k-1} + \sum_{k=1}^{n}6k$

$\sum_{k=1}^{n-1}s_k + s_n = s_0 + \sum_{k=1}^{n-1}s_{k} + 6\frac{n(n+1)}{2}$

$s_n = 7 + 3n(n+1) = 3n^2 + 3n + 7$

As you can see, this technique can easily be used in any cases where you have $s_k = s_{k-1} + f(k)$ and the sum of $f(k)$ up to $k = n$ can be fairly easily determined.

More generally, your question is a fairly simple example of Linear Recurrence Relations with Constant Coefficients. You can use a certain technique of a characteristic equation, as described in that link, to directly determine the solution of even considerably more complicated such equations.