How do you find an equation for this function that is not recursive?
f(n)=-2f(n-1)+(-1)^n(n-1)
Thanks in advance!
Thanks in advance!
3 Answers
Explanation:
I will assume that this is a function of integers, since otherwise there are many possible variations.
Given:
f(n) = -2f(n-1)+(-1)^n(n-1)
Let:
g(n) = (-1)^n f(n)
Then:
g(n) = (-1)^n f(n)
color(white)(g(n)) = (-1)^n (-2f(n-1)+(-1)^n(n-1))
color(white)(g(n)) = (-1)^n (-2(-1)^(n-1)g(n-1)+(-1)^n(n-1))
color(white)(g(n)) = 2g(n-1)+(n-1)
Let:
k = g(0)
Then
k ,2k ,4k+1 ,8k+4 ,16k+11 ,32k+26 ,...
Putting
0, 0, 1, 4, 11, 26,...
This has differences:
0, 1, 3, 7, 15,...
recognisable as
Let us compare the previous sequence with
1, 2, 4, 8, 16, 32,...
A matching formula is:
2^n-n-1
So the general formula for
g(n) = 2^n(k+1)-n-1
So the formula for
f(n) = (-1)^n(2^n(k+1)-n-1)
See below.
Explanation:
This is a linear difference equation. It can be solved as
To solve
for the particular we make
and finally
This formulation can be simplified a lot but we let this task to the reader.
NOTE
now making
Explanation:
The equation
can be rewritten in the form
This shows that the function,
obeys
The obvious solution for this equation is
Since
and so