1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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

    S&S

    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

    HallsofIvy

    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

    S&S

    User Avatar

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




Loading...
Similar Threads for Recurrence Equation Date
Setting up a matrix from a linear equation Apr 15, 2018
Recurrence relation Nov 16, 2016
Initial conditions for recurrence relation Nov 16, 2016
Recurrence relations Apr 1, 2015
Recurrence relation proof Mar 25, 2015