# Generating function counting quaternary sequence.

I have the following problems:

$1.$ Calculate the number of the n-digits Quaternary sequence containing even $"2"$ and $"1"$ and at least one $"3"$. (When a sequence is made by the digits $1,2,3,4$)

What I did: I figured that representing $1,2,3,4$ by $u,v,w,x$ gives us that the generating function for all Quaternary sequences is $$(u+v+w+x)^n$$ therefore the n-digits sequences with even $"1"$ is $$\frac{1}{2} \left((u+v+w+x)^n + (-u+v+w+x)^n\right)$$ and with even $"1"$ and $"2"$ is $$\frac{1}{4} \left((u+v+w+x)^n + (-u+v+w+x)^n\right) + \frac{1}{4} \left((u-v+w+x)^n + (-u-v+w+x)^n\right)$$ now I only want to count them so I can put $u=v=w=x=1$ and get a result, but I have no idea how to "spice it" so it will also include at least one $"3"$. If someone can shed some light it will be much appreciated.

$2.$ the next problem which I have absolutely no idea how to approach to:

Prove using generating functions that for $n<l$ $$\sum_{k=0}^{\infty}\sum_{i=n}^{l}\dbinom{2i}{k}=\frac{2^{2l+2}-2^{2n}}{3}$$

any suggestion?

• Your last equation does not have an $n$ on the left-hand side. Should there be an $n$ on top of the inner sum symbol? – john_leo May 23 '14 at 9:24
• hmmm nope, that's exactly how the question is written. – user114138 May 23 '14 at 9:27
• you are right. there's a mistake with the question! – user114138 May 23 '14 at 9:29
• Fixed it. sorry for the misunderstanding- my teacher's mistake :) – user114138 May 23 '14 at 9:32
• You are asking two distinct questions. Please make it into two separate questions. What would you do if you wanted to accept two answers from distinct users ? – Tom-Tom May 23 '14 at 15:09

• Even number of 1 (or 2): $1 + \frac{z^2}{2!} + \frac{z^4}{4!} + \dotsb = \frac{\mathrm{e}^z - \mathrm{e}^{-z}}{2}$
• At least one 3: $\frac{z}{1!} + \frac{z^2}{2!} + \frac{z^3}{3!} + \dotsb = \mathrm{e}^z - 1$
• Any number of 4: $1 + \frac{z}{1!} + \frac{z^2}{2!} + \frac{z^3}{3!} + \dotsb = \mathrm{e}^z$
Multiply all, extract $n!$ times the coefficient of $z^n$:
\begin{align} n! [z^n] \frac{\mathrm{e}^z - \mathrm{e}^{-z}}{2} \cdot \frac{\mathrm{e}^z - \mathrm{e}^{-z}}{2} \cdot (\mathrm{e}^z - 1) \cdot \mathrm{e^z} &= n! [z^n] \frac{1}{4} \left( \mathrm{e}^{4 z} - \mathrm{e}^{3 z} - 2 \mathrm{e}^{2 z} + 2 \mathrm{e}^{z} + 1 - \mathrm{e}^{-z} \right) \\ &= \frac{1}{4} \left( 4^n - 3^n - 2 \cdot 2^n + 2 + [n = 0] - (-1)^n \right) \end{align}
Here $[P]$ is Iverson's bracket, $1$ is the proposition $P$ is true, $0$ otherwise.