1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Thank you, great answer. I will try going from here. Just to make it clear to me, after calculating what equals $A(x)$ I need to do coefficient comparison right? $\endgroup$ – Gabi G Sep 9 '17 at 22:21
  • $\begingroup$ Yes, once you have $A(x)$, to find the "original" $a_k$ there are several ways, the most common one is by inspection , see eg here math.stackexchange.com/questions/251063/… $\endgroup$ – leonbloy Sep 9 '17 at 22:26
1
$\begingroup$

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)}} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.