Recurrence relation

Printable View

October 13th 2010, 04:46 PM
nurdynik

Recurrence relation

Solve the recurrence relation
$h_n = h_{n-1} + n^3$
with the initial condition $h_0 = 0$ , and verify your solution by induction on n.
October 14th 2010, 08:07 AM
Hugal

Didn't you forget some $h_{n+1}$ ? :/

'Cause your relation is true just for $n=1$ no matter the value of $h_1$

Hugal
October 16th 2010, 02:42 AM
Hugal

Ok ! I got what you meant. It is :

$\displaystyle h_n = h_{n-1}+n^3$

right ?

So, now just try to figure out what the first terms of this sequence are.
Try to find $h_1, h_2, h_3, h_4$ and you'll have quite a good idea of what actually the sequence is.
After that, you'll have to prove this. Induction is an easy way to make it.
Good luck,

Hugal
October 16th 2010, 05:16 AM
Plato

Quote:

Originally Posted by nurdynik

Solve the recurrence relation
$h_n = h_{n-1} + n^3$
with the initial condition $h_0 = 0$ , and verify your solution by induction on n.

See this webpage.
October 16th 2010, 06:26 AM
chisigma

Quote:

Originally Posted by nurdynik

Solve the recurrence relation
$h_n = h_{n-1} + n^3$
with the initial condition $h_0 = 0$ , and verify your solution by induction on n.

The solution is well known...

$\displaystyle h_{n} = \sum_{k=0}^{n} k^{3} = \frac{n^{2}\ (n+1)^{2}}{4}$

Kind regards

$\chi$ $\sigma$
October 16th 2010, 06:39 AM
Soroban

Hello, nurdynik!

Quote:

Solve the recurrence relation: . $h_n \:=\: h_{n-1} + n^3,\;\;h_0 = 0$
and verify your solution by induction on $n.$

Crank out the first few terms and you may see a pattern.

. . $\begin{array}{cc} n & h_n \\ \hline 0 & 0 \\ 1 & 1 \\ 2 & 9 \\ 3 & 36 & 4 & 100 \\ 5 & 225 \\ \vdots & \vdots \end{array}$

We see that the terms of the sequence are squares,
. . not every consecutive square,
. . but squares of certain numbers.

. . $\begin{array}{ccccc} 0 &=& 0^2 &=& (0)^2 \\ 1 &=& 1^2 &=& (0\!+\!1)^2 \\ 9 &=& 3^2 &=& (0\!+\!1\!+\!2)^2 \\ 36 &=& 6^2 &=& (0\!+\!1\!+\!2\!+\!3)^2\\ 100 &=& 10^2 &=& (0\!+\!1\!+\!2\!+\!3\!+\14)^2 \\ \vdots && \vdots && \vdots \end{array}$

These are the squares of Triangular Numbers, starting with $T_0 = 0.$

$\text{Therefore: }\;h_n \;=\;\left[\dfrac{n(n+1)}{2}\right]^2$