PDA

View Full Version : Recursive functions


kari1818
Mar 9, 2008, 03:20 PM
f(0)=7
f(n)=n^2 - f(n-1)

I have no idea how to do this, so any help will be appreciated:D

ebaines
Mar 10, 2008, 10:23 AM
Assuming that n takes on vaues 0, 1,2, 3... You already know that f(0) = 7. To find f(1), use the equation you were given with n = 1. Continue for n= 2, 3, 4, etc.

f(1) = 1^2 - f(0) = 1 - 7 = -6
f(2) = 2^2 - f(1) = 4 - (-6) =10
f(3) = 3^2 - f(2) = 9 - 10 = -1
etc.

galactus
Mar 11, 2008, 05:51 AM
Perhaps we can find a closed form. If we look close there is a pattern amongst the ven and odd recursions. I will use a_{n} instead of f_{n}.

a_{0}=7 \;\ \;\ \;\ a_{1}=-6

a_{2}=10 \;\ \;\ \;\ a_{3}=-1

a_{4}=17 \;\ \;\ \;\ a_{5}=8

a_{6}=28 \;\ \;\ \;\ a_{7}=21

.
.
.
.

Using finite difference or what not we find the closed form for the evens is

\frac{1}{2}n^{2}+\frac{1}{2}n+7

For the odds:

\frac{1}{2}n^{2}+\frac{1}{2}n-7

Combine the two and get:

\frac{1}{2}n^{2}+\frac{1}{2}n+(-1)^{n}\cdot{7}

Which can be written as \frac{n(n+1)}{2}+(-1)^{n}\cdot{7}

Notice the formula for the sum of the integers, plus or minus 7.