Sequences solutions with generating functions

Question

The task is to find $a_n$ (using generating functions preferably) when $a_0 = 1$ and for every $n\ge 0$ $$a_{n+1} = \frac{1}{3} \sum_{k=0}^{n} (8-5(-2)^k)\,a_{n-k}$$

I marked $b_n = \frac{1}{3}(8-5(-2)^n)$ and found the generating function $$g(x) = \sum_{n=0}^{\infty} \frac{1}{3}(8-5 (-2)^n)x^n = \frac{1+7x}{(1-x)(1+2x)}$$

I know that for suppose $t_n$ and $p_n$ are sequences with generating functions $f(x)$ and $p(x)$ then the generating function $h(x) = t(x)p(x)$ is for the sequence $$d_n = \sum_{k=0}^{n} t_{k} \, p_{n-k}$$ I know I need to use this here but I'm not really sure how.

Answer 1

You are in the right track in invoking the convolution property of GF:

$$d_n = \sum_{k=0}^{n} t_{k} \, p_{n-k} \tag{1}$$

(Recall that this assumes we are using sequences indexed on the non-negative integers)

The problem here is that we have $a_k$ (our unknown) on both sides of the equation.

Then let define the sequence $$ u_n = a_{n+1}=\sum_{k=0}^{n} b_k \, a_{n-k} \tag{2}$$ for $n\ge0$

Let $A(x),B(x),U(x)$ be the GF of $a_k,b_k,u_k$.

Then, using $ u_n = a_{n+1} $ we get (shifting property): $$U(x) = \sum_{n=0}^\infty x^n u_n= \sum_{n=0}^\infty x^n a_{n+1}= \sum_{j=1}^\infty x^{j-1} a_j = x^{-1} (A(x) -a_0) \tag{3}$$

Putting this together with the convolution property: $$U(x)=A(x)B(x)\tag{4}$$

and, given $a_0=1$, we get

$$A(x)=\frac{1}{1-x B(x)}$$

Can you go on from here?

Answer 2

Very good for the first part.

For continuing, the best approach is to include the starting conditions in the recurrence.
So you will write $$ a_{\,n} = \sum\limits_{0\, \le \,k\, \le \,n - 1} {b_{\,n - 1} \,a_{\,n - 1 - k} } + \left[ {0 = n} \right] $$ where $[P]$ denotes the Iverson bracket.

Then multiplying by $x^n$ and summing $$ \eqalign{ & f(x) = \sum\limits_{0\, \le \,n} {a_{\,n} \,x^{\,n} } = \cr & = \sum\limits_{0\, \le \,n} {\left( {\sum\limits_{0\, \le \,k\, \le \,n - 1} {b_{\,n - 1} \,a_{\,n - 1 - k} } } \right)\,x^{\,n} } + \sum\limits_{0\, \le \,n} {\left[ {0 = n} \right]\,x^{\,n} } = \cr & = x\sum\limits_{0\, \le \,n} {\left( {\sum\limits_{0\, \le \,k\, \le \,n - 1} {b_{\,n - 1} \,a_{\,n - 1 - k} } } \right)\,x^{\,n - 1} } + 1 = \cr & = xg(x)f(x) + 1 \cr} $$

you get $$ f(x) = {1 \over {1 - xg(x)}} $$