Math Is Fun Forum

priyankshah

Member

Registered: 2011-02-08

Posts: 5

recurrence

hello everybody

Can anyone help how to solve recurrence relation

T(n0 = T(n-2) + n^2  ?

Bob

Administrator

Registered: 2010-06-20

Posts: 10,140

Re: recurrence

hi priyankshah

Strictly, there ought to be a 'starting value ' as well, eg. T0 = 0, but I've managed a formula anyway.

I have a vague feeling there's a quick way to do these but I haven't managed to drag it into my conscious brain so you'll have to settle for the long route for now.

Firstly, I wanted to see what this sequence looked like with some numbers.  So I assumed the first term (n=0) is zero and got

0,1,4,10,20,35,56,84,120,165,220,.......

Then I made a table of differences, Tn - Tn-1, and got

1,3,6,10,15,21,.... which is the triangle numbers and can be formed by a quadratic.

That means your sequence is a cubic.

So I called it

and used four terms to create four simultaneous equations.

If you want to know the values they are here:

Hope that helps.  If I remember the quick way, I'll post again.

Bob

Last edited by Bob (2011-02-24 02:23:06)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

soroban

Member

Registered: 2007-03-09

Posts: 452

Re: recurrence

. .

. .

. .

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

. .

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

. . . . . . .

.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: recurrence

Hi priyankshah,

The characteristic equation of the homogeneous equation is:

Assume the particular solution to be:

Substitute it in the first equation and simplify:

Equating the co-efficients to 0 and solving, we get:

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

byronjordan

Member

Registered: 2011-01-30

Posts: 14

Re: recurrence

Nice, and perhaps obviously, to solve for a and b,

if T(0) and T(1) are givens.

If T(0)=0 and T(1)=1, then a=0 and b=0. However, if T(0) and T(1) are the initial conditions but are not given, then

If the course isn't this advanced, it might still be necessary to solve four simultaneous linear equations to solve for c, d, e, and f for n:even and n:odd, ignoring the a and b terms. The equations will be the same for n:even and n:odd if T(0)=0 and T(1)=1. If T(0) and T(1) are givens, but the values are not specified, T(0) and T(1) become terms in the solutions for n:even and n:odd, respectively, and the values of f are not the same for n:even and n:odd.

Last edited by byronjordan (2011-02-24 06:01:22)

priyankshah

Member

Registered: 2011-02-08

Posts: 5

Re: recurrence

Thank you for help!!1 really appreciate it

Bob

Administrator

Registered: 2010-06-20

Posts: 10,140

Re: recurrence

hi priyankshah,

You are very welcome.  I've worked out my 'other method' and it might be useful to learn.  It uses something called the 'method of differences'.  Post back if you want to learn more.  (less algebra and more number crunching involved)

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob