Recursion Question using Generating Functions

Question

Here is my question:

Consider the recurrence, $$a_{n+1}=2a_n+(-1)^n$$ with initial condition, $$a_0=0$$

Find and prove a formula for $a_n$.

I don't really know how to prove this formula

I tried going with a generating function method, but that kind of led nowhere.

Answer 1

The sequence generated by the recurrence relation is; $$0, 1, 1, 3, 5, 11, 21, \dots$$ Write the recurrence relation as; $$a_n-2a_{n-1}=(-1)(-1)^n$$ Get the generating function, $GF$ in the standard way; $$GF=0+x+x^2+3x^3+5x^4+11x^5+21x^6+\dots$$ $$-2xGF=0+0x-2x^2-2x^3-6x^4-10x^5-22x^6+\dots$$ $$(1-2x)GF=0+x-x^2+x^3-x^4+x^5-x^6+x^7-x^8+ \dots$$ $$(1-2x)GF=-\big(\frac{1}{1+x}\big)+1$$ $$GF=\frac{x}{(1-2x)(1+x)}$$ Use partial fractions to get; $$GF=\frac{1}{3}\times \frac{1}{1-2x}-\frac{1}{3}\times \frac{1}{1+x}$$ These are standard bits that translate directly into the formula; $$a_n=\frac{1}{3}2^n-\frac{1}{3}(-1)^n$$ or $$a_n=\frac{2^n-(-1)^n}{3}$$ Check this gives the sequence expected, which it does!

Answer 2

Hint.

Calling

$$ G(x) = \sum_{k=0}^{\infty}a_k x^k $$

we have

$$ a_{k+1}x^k-2a_k x^k -(-1)^k x^k = 0 $$

or

$$ \frac 1x\sum_{k=1}^{\infty}a_k x^k - 2\sum_{k=0}^{\infty}a_k x^k-\sum_{k=0}^{\infty}(-1)^k x^k = 0 $$

now assuming $|x| < 1$ we have

$$ \frac 1x (G(x)-a_0)-2G(x)-\frac{1}{x+1}=0 $$

and

$$ G(x) = \frac{a_0}{1-2x}+\frac 13\frac{1}{1-2x}-\frac 13\frac{1}{1+x} $$

etc.