finding explicit formula

Question

The question ask us to guess an explicit formula for the sequence

$$y_k = y_{k-1} + k^2 ,$$ for all integers $k$ greater than or equal to 2 and $y_1 = 1$

Can someone help me with this? so far what I got is this: $y_2 = 1 + 2^2$ $y_3 = 1 + [2^2 + 3^2]$ $y_4 = 1 + [2^2 + 3^2 + 4^2]$

How do I convert those in the bracket into a formula? Thanks in advance.

Answer 1

This is a well known series, given by $y_k= 1/6\, k(k+1)(2k+1)$. There are several methods to prove it. One of the standard approaches is by induction. A simple and intuitive method is the following:

1 - write the sequence of differences between consecutive terms: $1, 4, 9, 16...$;

2 - write the sequence of differences between consecutive terms of the previous sequence: $1, 3, 5, 7...$;

3 - again, write the sequence of differences between consecutive terms of the previous sequence: $2, 2, 2, 2...$.

Because the terms of this third sequence are constant, the sum is a cubic of the form $ak^3+bk^2+ck+d$. Since the sum is zero for $k=0$, it follows that $d=0$. Then, we can identify coefficients rewriting the equation $ak^3+bk^2+ck$ with $k=1$, $k=2$, and $k=3$ (for which we know the corresponding results $1, 5, 14$) obtaining the following three equations:

$$a+b+c=1$$

$$8a+4b+2c=5$$

$$27a+9b+3c=14$$

The, we can solve the system, getting $a=1/3$, $b=1/2$, and $c=1/6$. This leads to

$$1/6\,(2k^3+3k+k)=1/6 \, k(k+1)(2k+1)$$

Answer 2

$y_n=1+1/6\cdot n(n+1)(2n+1)-1=1/6\cdot n(n+1)(2n+1)$, because $\sum_{k=1}^n k^2=1/6\cdot n(n+1)(2n+1)$

-

Answer 3

Approach 1 (fast): rewrite it as $$ a_k -a_{k-1} =k^2\\ \Delta a_k = k^2 $$ This is a telescoping sum on the left (check this!). If you sum from 1 to $n$ you get $$ a_n - a_1 = \sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}{6} $$ The closed form expression can be obtained by using perturbation method or induction.

Approach 2 (hard and long). Use the generating function. It is $G(z) = \sum_{k=1}^{\infty} a_k z^k$. Then you need to solve $$ \frac{G(z)}{z} = G(z) + \sum_{k=1}^{\infty} k^2 z^k $$ which was obtained by multiplying RHS and LHS by $z^k$ and summing over $k$. Now do the algebra and get an expression of the form $$ \sum_{k=1}^{\infty}a_k z^k = \sum_{k=1}^{\infty} \varphi(k) z^k $$ You will find $\varphi(k)$ after some quick algebra. The closed-form solution will be $$ a_n = \varphi(n) $$