Finding a Non-Recursive Formula

Date: 06/10/99 at 13:32:16
From: Gabriel Alume
Subject: Method of iteration

I cannot for the life of me see the pattern in this problem based 
on iteration. I understand that once you find a pattern in the 
solutions to the recurrence relation, you guess a formula to solve. Am 
I not seeing something? Because I can't find a pattern. Please help.

recurrence relation: s_n = - [s_(n-1)] - n^2

initial condition:  s_0 = 3

s_1 = -4
s_2 = 0
s_3 = -9
s_4 = -7
s_5 = -18

Date: 06/10/99 at 17:21:25
From: Doctor Anthony
Subject: Re: Method of iteration

  The recurrence relation is

     u(n) + u(n-1) = -n^2

   Let u(r) = v(r) + w(r) where v(r) is solution of  v(r) + v(r-1) = 0 
 

So we solve   x + 1 = 0   x= -1   and v(r) = A.(-1)^r

and we use a trial solution  w(r) = a.r^2 + b.r

Substituting into the equation

          a.r^2 + b.r + a(r-1)^2 + b(r-1) = -r^2

   a.r^2 + b.r + a(r^2 - 2r + 1) + b(r-1) = -r^2

                  2a.r^2 + r(2b-2a) + a-b = -r^2

                   2a.r^2 + 2r(b-a) + a-b = -r^2

comparing coefficients of r on both sides we require a = -1/2,
b = a = -1/2

and so w(r) = -(1/2)[r^2 + r]

Therefore the general solution is

   u(n) = A(-1)^n - (1/2)[n^2 + n] 

and the initial condition is u(0) = 3  so  A = 3

We get

   u(n) = 3(-1)^n - (1/2)[n^2 + n]

Check with n = 5

        u(5) = -3 - (1/2)[25 + 5]

             = -3 - (1/2)(30)

             = -3 - 15

             = -18      which checks.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/