0
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – john_leo
    May 23, 2014 at 9:24
  • $\begingroup$ hmmm nope, that's exactly how the question is written. $\endgroup$
    – user114138
    May 23, 2014 at 9:27
  • $\begingroup$ you are right. there's a mistake with the question! $\endgroup$
    – user114138
    May 23, 2014 at 9:29
  • $\begingroup$ Fixed it. sorry for the misunderstanding- my teacher's mistake :) $\endgroup$
    – user114138
    May 23, 2014 at 9:32
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – Tom-Tom
    May 23, 2014 at 15:09

1 Answer 1

0
$\begingroup$

You want sequences, so you have to use exponential generating functions (the positions label your digits). Assuming there are "infinite" of each digit available to simplify, you have:

  • 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .