aboutsummaryrefslogtreecommitdiff
path: root/tech-math/comb/hw5.tex
blob: b20efb0e4d6523f8422eb75a6236836e824a513e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}}
\noindent {\bf Q1)} %#2

\pre{a.}
$$\sum_{i=0}^\infty x^{i+1} = {x \over 1-x}$$

\pre{c.}
$$\sum_{i=0}^\infty 2^ix^i = {1 \over 1-2x}$$

\pre{d.}
$$\sum_{i=0}^\infty x^{i+4} = {x^4 \over 1-x}$$

\pre{f.}
$$(2+x)^8$$ %%BUG BUG BUG

\pre{i.}
$$3+2x+4x^2+x^3\sum_{i=0}^\infty x^i = 3 + 2x + 4x^2 + {x^3 \over 1 - x}$$

\noindent {\bf Q2)} %#7

The generating function for $x_1$ is $1 \over 1-x$ because it is possible for all $n$. For $x_2$, $x^2 \over 1-x$ because there is no way of satisfying the restriction for $n<2$. For $x_3$, $1 \over 1-x^4$ as it is impossible for $n \not\equiv 0 ({\rm mod} 4)$ and $1+x+x^2+x^3$ for $x_4$ (because it cannot be all of the partition for $n$ more than $4$). One must also consider a fictional $x_5$ to account for the solutions which sum to less than $n$. This has the generating function $1 \over 1-x$. The combined possible number of solutions $c_n$ is the value of the coefficient for $x^n$ in their product. The product is $$x^2(1+x+x^2+x^3) \over (1-x)^3(1-x^4),$$ but by the fact that $$1+x+x^2+x^3={1-x^4 \over 1-x},$$ this is equal to $$x^2 \over (1-x)^4.$$

This, in closed form, becomes $${x^2 \over 6}\sum^\infty_{n=0} n(n-1)(n-2)x^{n-2}
= \sum^\infty_{n=0} {n(n-1)(n-2) \over 6}x^n
= \sum^\infty_{n=0} {n \choose 3}x^{n-1}
= \sum^\infty_{n=-1} {n+1 \choose 3}x^n,$$
giving a number of solutions $n+1 \choose 3$



\noindent {\bf Q3)} %#9

$$\sum^\infty_{n=0} {n \choose p}x^n$$

Note: in this problem and Q2, I used 0 and infinity as my bounds (mostly) because ${k \choose n}=0$ for $k<0$ and $k>n$.

\noindent {\bf Q4)} %#21

\pre{a.}
$a_n = 7^n$

\pre{b.}
$$x^2e^{3x}
= x^2\sum^\infty_{n=0} {(3x)^n \over n!}
= x^2\sum^\infty_{n=0} {3^n x^n \over n!}
= \sum^\infty_{n=0} {3^n x^{n+2} \over n!}
= \sum^\infty_{n=2} {3^{n-2} x^n \over {n-2}!}
= \sum^\infty_{n=2} {3^{n-2} x^n \over {n-2}!}
= \sum^\infty_{n=2} {3^{n-2}(n)(n-1) x^n \over n!}.$$

This shows $a_n = n(n-1)3^n$.

\pre{c.}
$a_n = (-1)^n n!$

\pre{d.}
\def\mod#1{\thinspace(\thinspace{\rm mod} #1)}
$$e^{x^4} = 1 + x^4 + {x^8 \over 2!} \dots $$
$$a_n = \left\{{ 0 : n\not\equiv 0 \mod{4} \atop {n! \over {n\over 4}!}: n\equiv 0\mod{4} }\right\}$$

\bye