# Homework Help: Recurrence Equation.

1. Nov 2, 2005

### S&S

Here is the famous thing, sum of k from 1 to n is n*(n+1)/2.

I'm trying to show this by recurrence equation. Then an is the sum, I have this equation: an=a(n-1)+n. It's not a*(n-1), just like this kind equations n indicates the number of the term.

The charcteristic equation is r^2-r-n=0. I found the roots of r with n in it. Continue solve the coefficients became quite complicated.

Am I doing right? Other good ideas?

2. Nov 2, 2005

### Benny

If you mean $$a_n = a_{n - 1} + n$$ then the characteristic equation should be a first degree polynomial. The solution of which is just x(or which ever variable you are using) = 1 giving you the homogeneous solution a_n = A, where A is constant.

3. Nov 3, 2005

### HallsofIvy

The characteristic equation to an+1= an is r= 1 (as Benny said, it is first degree because you recurence is first order). The "n" doesn't count because the characteristic equation is only true for homogeneous equations. Of course, again as Benny said, r=1 means that the solution to the homogeneous equation is an= A, a constant. Now you need to find a single solution to the entire equation, by "undetermined coefficients", to add to that. Since "n" is first degree, and your equation is first order, Normally we would try a first degree function: an= un+v where u and v are numbers. However, since a constant is alread a solution to the homogenous equation, multiply by n: try an= un2+ vn.
Then an+1= u(n+1)2+ v(n+1)= un2+ 2un+ u+ vn+ v= un2+ (2u+ v)n+ (u+v). The equation an+1= an+ n becomes un2+ (2u+ v)n+ (u+v)= un2+ (v+1)n.
We have three equations for u, v: u= u, 2u+ v= v+1 and u+v, which reduce to just 2: u= 1/2 and u+ v= 0 so v= -1/2. an= (1/2)n2- (1/2)n= (1/2)(n)(n-1).
The general solution, where a0 is any constant, is an= a0+ (1/2)(n)(n-1).

4. Nov 3, 2005

### S&S

guys you rock.