# Recurrence relation

Printable View

• Oct 13th 2010, 05: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.
• Oct 14th 2010, 09: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
• Oct 16th 2010, 03: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
• Oct 16th 2010, 06: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.
• Oct 16th 2010, 07: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$
• Oct 16th 2010, 07: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$