How Do You Solve the Recurrence Relation a_n = a_{n-1} + n?

[Darth Frodo]

Homework Statement

$a_{n} = a_{n-1} + n$
$a_{0} = 0$

The Attempt at a Solution

$h_{n} = h_{n-1}$
$t^{2} - t = 0$
$t=0 t=1$
$h_{n} = B$

$p_{n} = bn + c$
$p_{n} = p_{n-1} + n$
$bn + c = b(n-1) + n$
$bn + c = (b+1)n -b$

I'm sure I've gone wrong somewhere, I just can't figure out where!

 

[mfb]

$bn + c = b(n-1) + n$

I think there is a "+c" missing on the right side.

I have no idea how the first 2 and the following 4 lines are related to the other groups.

 

[Darth Frodo]

Ok sorry I should have explained.

Basically, how I solve a nonhomogenous RR is by ignoring the nonhomogenous term, and solving the homogenous term, 1st group.

Then I solve the homogenous term by picking a particular function of the same order of the nonhomogenous part and call this Pn. This is the second group.

Then, the General Solution to the RR is $h_{n} + p_{n}$


Yes you're right. So with the correction I get the following.

$p_{n} = bn + c$
$p_{n} = p_{n-1} + n$
$bn + c = b(n-1) + c + n$
$bn + c = (b+1)n -b + c$

I don't know how to solve for b and c I'm afraid.

 

[oli4]

Hi Darth Frodo, aren't you just trying to solve a simple arithmetic serie ?
u(n)=n
a(n)=1+2+...+n=n(n+1)/2 ?

 

[mfb]

The solution for a_n cannot be expressed as sum of a constant (h_n) and bn+c with constant b and c.

Hi Darth Frodo, aren't you just trying to solve a simple arithmetic serie ?

Right.

 

[SammyS]

Homework Statement

$a_{n} = a_{n-1} + n$
$a_{0} = 0$

Please, give a complete statement of the problem.

My mind-reading skills seem to be eroding lately.

 

[HallsofIvy]

If the problem is to solve $a_n= a_{n-1}+ n$, $a_0= 0$, then most of what you are doing is unnecessary. Instead, first calculate a few values directly:
$a_1= a_0+ 1= 0+ 1= 1$
$a_2= a_1+ 2= 1+ 2= 3$
$a_3= a_2+ 3= 3+ 3= 6$
$a_4= a_3+ 4= 6+ 4= 10$
$a_5= a_4+ 5= 15$

In other words, [itex]a_n= 1+ 2+ 3+ 4+ \cdot\cdot\cdot+ n[/tex], an arithmetic series as both oli4 and mfb said, for which there is a well known formula[/itex]