Mryntu

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
$,

$beginarray\
s_n+1
&=s_n+6(n+1)\
&=3n^2+3n+7+6(n+1)\
&=3n^2+9n+13\
endarray
$

If your hypothesis is true,
then

$beginarray\
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\
endarray
$

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 tag1labeleq1$$

Summing both sides of eqrefeq1 from $1$ to $n$ gives that

$sum_k=1^ns_k = sum_k=1^ns_k-1 + sum_k=1^n6k$

$sum_k=1^n-1s_k + s_n = s_0 + sum_k=1^n-1s_k + 6fracn(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.$