How is the Recurrence Relation Used in Function Definitions?

[mubashirmansoor]

Hello everybody,

I wanted to know the uses of such a function definition;

f(x) = 3*f(x-1) - 3*f(x-2) + f(x-3) This works in linear and quadratic functions.

I'll thankfull for your replies :)

 

[matt grime]

In what way does that 'work in linear and quadratic functions'?

 

[mubashirmansoor]

In what way does that 'work in linear and quadratic functions'?

As an example; say x^2 & assuming x = 4

f(4) = 3*f(3) - 3*f(2) + f(1) which is true: 16 = 3*9 - 3*4 +1

this is what I meant...

Do you know any interesting uses of such a thing?
Thanks for contributing :)

 

[uart]

Let me explain how you can derive an equation like that one and why it works.

Say you started with a very simple linear recurrence relation,

1. f(x) = f(x-1) : This works for f(x) = 1.

Now let's look for one that works for f(x) = x and also for f(x) = 1.

Say f(x) = c f(x-1) + d f(x-2). Subst f(x)=1 and you find that "c+d=1". Next subst f(x)=x and you find that in addition to "c+d=1" we must also have "c + 2d = 0". Solving these give c=2 and d=-1. So our second recurance relation is,

2. f(x) = 2 f(x-1) - f(x-2) : This works with f(x) = 1 and with f(x) = x

Similar working with three simultaneous equations you can find the coefficients of a third order linear equation that works for f(x)=1 and for f(x)=x and for f(x)=x^2. This one turns out to be the one that you started this thread with. That is,

3. f(x) = 3f(x-1) - 3f(x-2) + f(x-3) : This works with f(x)=1 and with f(x)=x and with f(x)=x^2

Note that these are all linear mappings of the form, f(x) = L{ f(x-1), f(x-2), ...}

It is important to realize that these are all linear in "f", whether or not f is linear in x is irrelevant to this point.

By linearity L{ a f_1 + b f_2 + ... } = a L{f_1} + b L{f_2} + ...

So you can see for example that since the second relation above "works" for f_1(x)=1 and f_2(x)=x then it automatically must work for all linear functions f(x) = ax+b.

For the same reason the third relation must hold for all quadratic funtions and so on.

 

[mubashirmansoor]

Let me explain how you can derive an equation like that one and why it works.

Thankyou very much Uart, but I think I don't have enough knowledge of mathematics to understand this derivation but I'll certainly keep it in a safe place and check it out once I've learned more maths... Thanks once again :)

Actually I have derived this one by myself but using a very different technique which is given as follows;

lets say we have 3 consecutive terms; f(5), f(4) & f(3) .

f(5) - f(4) = rate of increase between these terms.

f(4) - f(3) = rate of increase between these terms, which is sth like first derivative.

Now ; f(5) - f(4) - ( f(4) - f(3) ) = rate of increase between the rates of increase which is sth like 2nd derivative.

2nd derivative of quadratic and linear functions is always constant, using this fact and a little logic we'll have;

f(5) - f(4) - ( f(4) - f(3) ) + ( f(5) - f(4) ) + f(5) = f(6)

which means; f(6) = 3*f(5) - 3*f(4) + f(3)

----------

Thats what I did...

So what are the uses of such function definitions?

One use of this was solving projectile motion without being concerned about the equation of motion & having quick estimates for many functions without trying to evaluate the function's eq. especially when concerned with an irregular function.

I'll be eagerly waiting for your reply :)
Thanks once again.

 

[truewt]

So the essentials of this method uart is doing is to think up of a recurrence relation and find let certain functions you want the recurrence relation to work with, to find out the exact recurrence relation? Relating the functions