2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$". $\endgroup$ – John Omielan Apr 19 at 20:24
  • $\begingroup$ Yes, of course. About such techniques one could read in the "Concrete mathematics" book by Graham, Knuth, Patashnik. $\endgroup$ – szw1710 Apr 19 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.