Homework #2:Text: 3.6.3, 3.8: 6,8,10,13 4.2: 8,9 4.3: 7,8,9,12,16
3.6.3: Proof #1: Use
$$
(1+x)^m*(1+x)^n=(1+x)^{m+n}
$$
and find the coeff of $x^k$ on both sides using the binomial theorem.
Proof #2: The right side counts the number of $k$-element subsets of the
$m+n$ element set $\{1,2,\cdots,n,n+1,\cdots, n+m\}.$ Any such subset $A$ is uniquely defined
by its intersection with $\{1,2,\cdots,n\}$ and $\{n+1,\cdots, n+m\}, $ say of sizes
$j$ and $k-j$. There are
$$
\binom{n}{j}\binom{m}{k-j}
$$
such sets and summing over all possible $j$ gives the identity.
3.8.6: You need to go 9 avenues and 19 streets so the answer is $\binom{19+9}{9}.$
3.8.8: By induction on $m,$ this reduces to Pascal's triangle for the binomial coeff. The second identity can be rewritten as $$ \sum_{k=m}^n \binom{n}{m}\binom{n-m}{k-m}=\binom{n}{m} 2^{n-m} $$ by the binomial thoerem.
3.8.10: Give the $k$ children 5 pennies. Then you have $n-5k$ stars and $k-1$ bars, for $\binom{n-5k+k-1}{k-1}.$
3.8.13: Suppose the middle element is $x$. Then $$ \binom{n}{2k+1}=\sum_{x=1}^n \binom{x-1}{k}\binom{n-x}{k}. $$
4.2.8: Use (4.5) with $a=k$ and $b=(n-1)k-1$ to obtain $$ F_{nk}=F_{k+1}F_{(n-1)k}+F_kF_{(n-1)k-1}. $$ Run an induction on $n$. By induction, $F_k$ divides $F_{(n-1)k}.$ Clearly $F_k$ divides the second term. So $F_k$ divides $F_{nk}.$ The base case is $n=1.$
4.2.9: The slopes of the quadrilaterals are 2/5 while the slope of the right triangles are 3/8. These are not equal, so the edges do not match. In general $F_n/F_{n+2}$ is close to $F_{n+1}/F_{n+3}$, but not equal.
4.3.7: Call this number $A_n$, so $A_0=1$, $A_1=2$, $A_2=4$, and $A_3=7.$
Take $n$ at least 3.
CASE 1: $n$ not in the set. We then have such a subset of $\{1,\cdots, n-1\}$, so
$A_{n-1}$ choices.
CASE 2: $n$ in the set but $n-1$ is not. This gives $A_{n-2}$ choices.
CASE 3: $n$ in the set, $n-1$ in the set, but $n-2$ is not. $A_{n-3}$ choices.
So
$$A_n=A_{n-1}+A_{n-2}+A_{n-3}.
$$
There are three roots to $x^3=1+x+x^2$, the lregest is about 1.8.3, exponential growth.
4.3.8: $2^{100}$ since it beats $1.6^{100}.$
4.3.9: (a) Induction on n: $n=1$ is $1=F_2=F_3-1=2-1.$ Adding $F_{2n}$ to the $n-1$ case yields
$F_{2n}+F_{2(n-1)}-1=F_{2n+1}-1$ by the Fibonacci recurrence.
(b) Write
$$
F_{n+1}^2-F_n^2=(F_{n+1}-F_n)(F_{n+1}+F_n)= F_{n-1} F_{n+2}
$$
by the Fibonacci recurrence.
(c) and (d): Let's do both of these at the same time.
Suppose we iterate the Fibonacci recurrence. We get
$$
F_N=F_{N-2}+2*F_{N-3}+F_{N-4}.
$$
If we do the Fibonacci recurrence $j$ times we get (by induction on $j$)
$$
F_N=\sum_{s=0}^j F_{N-j-s} \binom{j}{s}.
$$
Choosing $N=2n$, $j=n$ gives (c) and $N=2n+1$, $j=n$ gives (d).
4.3.12: Guessing $b_k=A^k$ gives $A^2=3A-2$ so $A=2$ or $A=1$. The general solution is $b_k=c1*2^k+c2*1^k$, find c1 and c2 from the initial conditions.
4.3.16: Let's prove (a) and (b) by induction, namely any positive integer $x \lt F_n$ can be
written as a sum of non-consecutive Fibonacci numbers.
CASE 1: If $x\lt F_{n-1}$ we are done by induction on $n$.
CASE 2: If $x=F_{n-1}$, this works with a single term.
CASE 3: If $F_{n-1}\lt x\lt F_n$, then $y=x-F_{n-1}$ satisfies
$1\le y \lt F_n-F_{n-1}=F_{n-2}.$ So by induction $y$ is a sum of Fibonacci numbers
whose indices are less than $n-2$ and non-consecutive. Adding $F_{n-1}$ to this sum works for
$x$.
(c) Strictly speaking this is not correct, for example $8=F_6=5+2+1=F_5+F_3+F_1.$ But $F_1=F_2=1$,
and $F_2$ and $F_3$ are consecutive. Let's prove it is true assuming that it means a 1 and
a 2 cannot both be allowed. We'll prove it is unique if $x \lt F_n$ by induction on $n$.
Base cases: $1, 2, 3 (2+1$ not allowed), $3+1, 5, 5+1, 5+2.$
Note that (4.3.9)(a) says $F_2+F_4+\cdots +F_{2n}=F_{2n+1}-1$ is the largest sum of non-consecutive Fibonacci numbers less than $F_{2n+1}$. Also note that $F_1+F_3+\cdots+F_{2n-1}=F_{2n}$, so the largest sum of non-consecutive Fibonacci numbers less than $F_{2n}$ which do not contain both $1$ and $2$ is $F_{2n}-1.$
Inductive case: Assume $x\lt F_n.$ If $x \lt F_{n-1}$ we are done by induction. Otherwise
$F_{n-1} \le x\lt F_{n}.$
CASE 1: $x=F_{n-1}$ which is a sum of non-consecutive Fibonacci numbers.
By the remark above all other sums of non-consecutive Fibonacci numbers less than $F_{n-1}$
are at most $F_{n-1}-1$, so the representation is unique.
CASE 2: $x \gt F_{n-1}.$ Then $y=x-F_{n-1}$ satisfies $1\le y \lt F_{n-2}.$ So by induction $y$ has
such a unique representation. Any representation of $x$ must involve $F_{n-1}$,
so we are done.
Additional Problems for HW #2
E1: (a) The coeff of $x^n$ on the right side is
$$
\sum_{k=0}^n \frac{1}{k!} (-1)^k
$$
which is $D_n/n!.$
(b) Note that the probability that a permutation of length $n$ has exactly $k$
fixed points is $\binom{n}{k} D_{n-k}/(n)!$. So we need to prove
$$
\sum_{k=0}^n \frac{D_{n-k}}{(n-k)!}\frac{k}{(k)!}=1.
$$
which is the coeff of $x^{n-1}$ in
$$
\frac{1}{1-x}= \frac{d}{dx}e^x*\sum_{j=0}^\infty D_j/j!*x^j
$$, so is 1.
This may also be easily done using the linearity of the expectation for random variables.
E2: Consider a derangement $\pi$ of $n$. Then $k=\pi_n\neq n.$
CASE 1: $\pi_k=n$, then the remaining $n-2$ entries of $\pi$ are a derangement
of $n-2$, so $D_{n-2}$ choices.
CASE 2: $\pi_k\neq n$. Then we have a derangement where the letter $n$ replaces the letter
$k$, $D_{n-1}$ choices.
Since $k$ has $n-1$ choices we have $D_n=(n-1)(D_{n-1}+D_{n-2}).$
E3: Let $S_i$ be the set of perms such that $i+1$ does immediately follow $i$. Then we need $|\overline S_1\cap \cdots \cap \overline S_{n-1}|.$ By the PIE, this is $$ \sum_{k=0}^{n-1} \binom{n-1}{k}(-1)^k (n-k)!=(n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!} (n-k) $$ which is, since we can add the $k=n$ term which is 0, $$ \sum_{k=0}^n n*(n-1)!*(-1)^k/k!-\sum_{k=1}^n (n-1)!*(-1)^k/(k-1)!=D_n+D_{n-1}. $$
E4: (a) All blocks have size 1 except a single block of
size 2, so the answer is $\binom{n}{2}.$
(b) We have either a single block of size 3, $\binom{n}{3}$ choices, or two blocks of size 2,
$\binom{n}{4}*3$ choices. So $S(n,n-2)=\binom{n}{3}+\binom{n}{4}*3$
a polynomial in $n$ of degree 4.
E5: This is $$ 1^2+2^2+\cdots (3n)^2-(3^2+6^2+\cdots (3n)^2)= 3n(3n+1)(6n+1)/6-9*n(n+1)(2n+1)/6. $$