Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Recurrence Equation.

  1. Nov 2, 2005 #1


    User Avatar

    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. jcsd
  3. Nov 2, 2005 #2
    If you mean [tex]a_n = a_{n - 1} + n[/tex] 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.
  4. Nov 3, 2005 #3


    User Avatar
    Science Advisor

    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).
  5. Nov 3, 2005 #4


    User Avatar

    guys you rock.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook