Iteration to guess formula and simplify and use mathematical induction to prove right

Question

I have this homework question, but my teacher didn't explain how to do these kind of problems too well. So basically the question is, Use iteration to guess an explicit formula for the sequence, then simplify it, and use mathematical induction to prove it correct. I'm having issues finding an explicit formula, and then proving it. If someone could show me how to find a formula for this and then simplify as much as possible and then prove its truth with mathematical induction, I'd be ever so thankful.

$$y_k=y_{k-1}+k^2$$ $$y_1=1$$

for all integers k is greater than or equal to 2

Answer 1

First, compute a bunch of terms. A spreadsheet makes it easy. By analogy with integration you might guess that the formula is cubic in the index. Find a cubic that fits four terms. Then assume the cubic is correct up to $k$, compute $y_{k+1}$ from the cubic and show that it satisfies the iteration.

Answer 2

it is not easy to see this pattern by inspection! however:

firstly we can see that we may set $y_0 = 0$, compatibly with the information provided.

if $y_k$ is a polynomial (see below) in $k$ then $y_0=0$ implies $y_k = k z_k$ for some other polynomial $z_k$.

direct substitution shows: $z_1 = 1, z_2 = \frac52, z_3 = \frac{14}3$.we may write these results as:

$$ \begin{align} 6z_1 &= 6 \\ 6z_2 &= 15 \\ 6z_3 &= 28 \end{align} $$

we may now recognize the numbers on the right as the triangular numbers $T_3, T_5, T_7$

this suggests we try: $$ 6z_k = T_{2k+1} = (k+1)(2k+1) $$ and thus: $$ y_k = \frac16 k(k+1)(2k+1) \tag{H} $$

to prove this hypothesis correct by induction requires us to show that: $$ y_{k+1} - y_k = k^2 $$ substituting from H we have: $$ 6(y_{k+1} - y_k) = (k+1)(k+2)(2k+3) - k(k+1)(2k+1) = (k+1)\bigg( 2k^2+7k+6 - (2k^2 +k)\bigg) = 6(k+1)^2 $$ so all is ok!

---

the hypothesis that $y_k$ is a polynomial of degree 3 can be vindicated by looking at the third-order differences: $$ y_{k+3} - y_{k+2} = (k+3)^2 \\ (y_{k+3} - y_{k+2}) - (y_{k+2} - y_{k+1}) = (k+3)^2 - (k+2)^2 = 2k+5 \\ \bigg((y_{k+3} - y_{k+2}) - (y_{k+2} - y_{k+1})\bigg) - \bigg((y_{k+2} - y_{k+1}) - (y_{k+1} - y_{k})\bigg) = 2 $$