# Induction Proof for Sequences

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.

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} + 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.

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

• My answer has one way to show what you're asking about, i.e., "if $s_{k}=s_{k-1}+6k$ and $s_0=7$, then $a_k=3k^2+3k+7$". – John Omielan Apr 19 at 20:24
• Yes, of course. About such techniques one could read in the "Concrete mathematics" book by Graham, Knuth, Patashnik. – szw1710 Apr 19 at 20:30