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!

3 Answers
Mar 30, 2018

f(n) = (-1)^n(2^n(k+1)-n-1)

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 g(0), g(1), g(2),... form a sequence:

k, 2k, 4k+1, 8k+4, 16k+11, 32k+26,...

Putting k=0, this sequence becomes:

0, 0, 1, 4, 11, 26,...

This has differences:

0, 1, 3, 7, 15,...

recognisable as 2^n-1

Let us compare the previous sequence with 2^n:

1, 2, 4, 8, 16, 32,...

A matching formula is:

2^n-n-1

So the general formula for g(n) can be written:

g(n) = 2^n(k+1)-n-1

So the formula for f(n) can be written:

f(n) = (-1)^n(2^n(k+1)-n-1)

Mar 31, 2018

See below.

Explanation:

This is a linear difference equation. It can be solved as

f(n) = f_h(n)+f_p(n) with

f_h(n)+2f_h(n-1) = 0
f_p(n)+2f_p(n-1)=(-1)^n(n-1)

To solve f_h(n) we make

f(n) = a^n and after substitution

a^n+2a^(n-1) = 0 rArr a = -2 rArr f_h(n) = (-1)^n 2^n

for the particular we make f_p(n) = c_n (-1)^n 2^n and after substitution

c_n(-1)^n2^n+2c_(n-1)(-1)^(n-1)2^(n-1) = (-1)^n(n-1) or

c_n-c_(n-1) = (n-1)2^-n or

c_n = c_(n-1) + (n-1)2^-n or

c_n = c_0 + sum_(k=1)^n (k-1)2^-k

and finally

f(n) = (c_0 + sum_(k=1)^n (k-1)2^-k)(-1)^n2^n

This formulation can be simplified a lot but we let this task to the reader.

NOTE

sum_(k=1)^n(k-1)x^k = x^2 sum_(k=0)^(n-1)x^k = x^2d/dx((x^n-1)/(x-1)) then

sum_(k=1)^n(k-1)x^k =(x (x + (n (x-1) - x) x^n))/(x-1)^2

now making x = 2^-1 we obtain

sum_(k=1)^n(k-1)2^-k =1-(n+1)2^-n

Apr 1, 2018

f(n) = (-1)^n[2^n(f(0)+1)-n-1]

Explanation:

The equation

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

can be rewritten in the form

f(n)+(-1)^n(n+1) = -2f(n-1)+(-1)^n{(n-1)+(n+1)}
qquad qquad = -2(f(n-1)+(-1)^(n-1) n)

This shows that the function, F(n), defined by

F(n) equiv f(n)+(-1)^n(n+1)

obeys

F(n) = -2F(n-1)

The obvious solution for this equation is

F(n) =(-2)^nF(0)

Since F(0) = f(0)+1, we have

F(n) equiv f(n)+(-1)^n(n+1) = (-2)^n(f(0)+1)

and so

f(n) = (-2)^n(f(0)+1) - (-1)^n(n+1)
qquad = (-1)^n[2^n(f(0)+1)-n-1]