Don't know what to do here, recursive problem

**HeadOnAPike** · October 12th 2009, 11:20 AM

The succession [Xsubn] is defined as

Xsub0 = 0, Xsub(n+1) = Xsubn + n(n+1)

Show that Xsubn = (1/3)(n-1)n(n+1).

I am assuming I am not allowed to use what I am demonstring as part of the proof. No clue what do despite staring at it for 15 minutes.

**Taluivren** · October 12th 2009, 11:51 AM

Hi,

$x_0 = 0$ , $x_{n+1} = x_n + n(n+1)$
and we have to prove $x_n = \frac{1}{3}(n-1)n(n+1)$ .

We proceed by induction:
$n=0$ .. $x_0 = \frac{1}{3}(0-1)\cdot 0\cdot (0+1) =0$ so the base case holds.

suppose the statement holds for $n$ and let's prove it holds for $n+1$ :
$x_{n+1}= x_n + n(n+1) = \frac{1}{3}(n-1)n(n+1) +n(n+1)$ (by induction hypotheses)
$= n(n+1)(\frac{1}{3}(n-1)+1) = n(n+1)(\frac{1}{3}n+\frac{2}{3}) = \frac{1}{3}n(n+1)(n+2)$
$=\frac{1}{3}((n+1)-1)(n+1)((n+1)+1)$ so the inductive step is done.

**HeadOnAPike** · October 12th 2009, 12:30 PM

My mistake was thinking you can't use the statement your trying to prove. But with induction you can. Thanks.

**HallsofIvy** · October 12th 2009, 07:28 PM

But it is perfectly valid to show that what you are given is a solution to an equation by putting it into the equation.

For example, it would be very difficult to solve $x^5- 6x^2- 3x- 2= 0$ but it is very easy to show that x= 2 is a solutions: [tex]2^2- 6(2^2)- 3(2)- 6= 32- 24- 6- 2= 0.

Similarly, here, you are not asked to solve the recursion, just to show that $x_n= \frac{(n-1)n(n+1)}{3}$ satisfies it. And that is basically what Taluivren did.

Thread: Don't know what to do here, recursive problem

LinkBack

Thread Tools

Display

Don't know what to do here, recursive problem

Similar Math Help Forum Discussions

A recursive relation table and proving problem...

A Recursive Function Problem in Mathematica

Primitive Recursive vs Recursive Functions

Recursive Deinition of order pairs problem

self-contradictory recursive problem

Search Tags