Solving Recurrence Equation: Understanding the Roots & Coefficients

[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?

 

[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.

 

[HallsofIvy]

The characteristic equation to a_n+1= a_n 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 a_n= 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: a_n= un+v where u and v are numbers. However, since a constant is alread a solution to the homogenous equation, multiply by n: try a_n= un²+ vn.
Then a_n+1= u(n+1)²+ v(n+1)= un²+ 2un+ u+ vn+ v= un²+ (2u+ v)n+ (u+v). The equation a_n+1= a_n+ n becomes un²+ (2u+ v)n+ (u+v)= un²+ (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. a_n= (1/2)n²- (1/2)n= (1/2)(n)(n-1).
The general solution, where a₀ is any constant, is a_n= a₀+ (1/2)(n)(n-1).

 

[S&S]

guys you rock.