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

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.