Tjyylli

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=3cdot(0)^2+3cdot(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.

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.

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} + 6frac{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.

It seems to me that induction is not needed here. Fix $kinBbb 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.$