Chapter 1 Recurrent Problems

Warmups

Homework exercises

1.8

List $Q_1$ through $Q_6$, we could find out that $Q$ is periodic.

$$\begin{array}{rl}{Q}_m& =\alpha ;\\ Q_{m+1}& =\beta ;\\ Q_{m+2}& =(1+\beta )/\alpha ;\\ Q_{m+3}& =(1+\alpha +\beta )/(\alpha \beta );\\ Q_{m+4}& =(1+\alpha )/\beta ,\text{for }m\in \{0,5,10,\dots \}\text{.}\end{array}$$

1.9a

$$\begin{array}{rl}{x}_1\dots x_n& \le {\left(\frac{x_1+\cdots +x_{n-1}+x_n}{n}\right)}^n\text{by }(n-1)x_n=x_1+\cdots +x_{n-1}\\ x_1\dots x_n& \le {\left(\frac{(n-1)x_n+x_n}{n}\right)}^n\\ x_1\dots x_{n-1}& \le (x_n{)}^{n-1}\\ x_1\dots x_{n-1}& \le {\left(\frac{x_1+\cdots +x_{n-1}}{n-1}\right)}^{n-1}.\end{array}$$

1.9b

$$\begin{array}{rl}{x}_1\dots x_n{x}_{n+1}\dots x_{2n}& \le {\left(\frac{x_1+\cdots +x_n}{n}\right)}^n{\left(\frac{x_{n+1}+\cdots +x_{2n}}{n}\right)}^n\text{by }P(2):x_1{x}_2\le {\left(\frac{x_1+x_2}{2}\right)}^2\\ & \le {\left(\frac{{\left(\frac{x_1+\cdots +x_n+x_{n+1}+\cdots +x_{2n}}{2}\right)}^2}{n^2}\right)}^n\\ & \le {\left(\frac{x_1+\cdots +x_n+x_{n+1}+\cdots +x_{2n}}{2n}\right)}^{2n}.\end{array}$$

1.9c

For example, $P(5)$ follows from $P(6)$ from $P(3)$ from $P(4)$ from $P(2)$ which is proved to be true. And whenever $n>1$, $P(n)$ is finally based on $P(2)$.

1.10

It’s clear that $Q_n=2R_n-1$ if we

1. move $n-1$ disks counter-clockwise;
2. move the largest disk clockwise;
3. move $n-1$ disks counter-clockwise again.

Then $R_n=2R_n+Q_{n-1}+2$ if we

1. move $n-1$ disks counter-clockwise;
2. move the largest disk clockwise;
3. move $n-1$ disks clockwise;
4. move the largest disk clockwise again;
5. move $n-1$ disks back counter-clockwise.

Plug $Q_n=2R_n-1$ in, then $R_n=Q_n+Q_{n-1}+1$.

1.11a

Move a double $(n-1)$-tower, then move the two largest disks, which takes $2$ moves, then move the double $(n-1)$-tower again. Let $A_n$ be the minimum number of moves, hence $A_n=2A_{n-1}+2=2^{n+1}-2$.

1.11b

Let $\sout{B_n}$ be the minimum number of moves to move a double $\sout{n}$-tower in the original order; $\sout{H_n}$ be the minimum number of moves to move a double $\sout{n}$-tower except for the bottom disk. Then we have $\sout{B_n=H_n+1+B_{n-1}+1+B_{n-1}}$ and $\sout{H_n=B_{n-1}+1+B_{n-1}}$.

Insert $\sout{H_n}$ to the $\sout{B_n}$ equation, we could get $\sout{B_n=4B_{n-1}+3=4^n-1}$.

By referring to the answer, I found out that my approach above wasn’t correct. I’ve made a mistake that I postulated all disks never change the order during their moves, which is not necessary.

It can be shown that no strategy does better than $B_n=A_{n-1}+2+A_{n-1}+2+B_{n-1}$. This strategy changes the order of bottom two disks twice but doesn’t care whether the upper disks keep the order during their moves, which is also the reason why we use $A_n$ here. Thus, $B_n=2^{n+2}-5$.

1.12

$$A(m_1,\dots ,m_n)=2A(m_1,\dots ,m_{n-1})+m_n.$$

This is an equation of the “generalized Josephus” type, whose solution is $(m_1\dots m_k{)}_2$.

1.13

We already know $n$ straight lines define $L_n=\frac{n(n+1)}{2}+1$ regions on a plane, and when the $n$-th line is added in, $n$ new areas are created.

Let the zig-zags be extremely narrow to be seen as straight lines to some extent. So when the $n$-th zig-zag is added in, $n$ new areas are created “in the straight line manner.”

We could also see that when two zig-zags intersect, $8$ new areas are created “around their intersection” in the way shown below:

And when the $n$-th zig-zag is added in, there are at most $n-1$ new “intersections.” So

$$Z{Z}_n=Z{Z}_{n-1}+n+8(n-1)=\frac{9}{2}{n}^2+\frac{7}{2}n+1.$$

1.14

$n$ new areas are created when the $n$-th line is added into the plane, which is equal to the maximum number of line segments created by splitting a line with $n-1$ points. Analogously, $L_{n-1}$ new pieces of cheese is created when making the $n$-th slice.

So, in recurrence form

$$P_n=\{\begin{array}{ll}1,& \text{if }n=0;\\ P_{n-1}+L_{n-1},& \text{if }n>0.\end{array}$$

We have $P_5=26$.

1.15

The function $I$ has the same recursion relation as $J$, but with different boundary values, which are $I(2)=2,I(3)=1$.

Thus, we cannot find a unique $I(1)$ that satisfies this recurrence. So we have to split it into two cases, one with $I(2)=2$ and one with $I(3)=1$.

Let’s represent in terms of $n=2^m+l$, and let ${\beta }_0=-1,{\beta }_1=1$. The recurrence unfolds, binary-wise:

$$\begin{array}{rl}I((b_m{b}_{m-1}\dots b_0{)}_2)& =2I((b_m{b}_{m-1}\dots b_1{)}_2)+{\beta }_{b_0}\\ & ⋮\\ & =2^{m-1}I((b_m{b}_{m-1}{)}_2)+\cdots +2{\beta }_{b_1}+{\beta }_{b_0}.\end{array}$$

Then we can stop here, so far the function $I$ have the same form as $J$, and the two leading bits $(b_m{b}_{m-1}{)}_2$ are enough to contain the two cases:

$$\begin{array}{rl}J(2)=1,I(2)=2& ⟹I(n)-J(n)=2^{m-1};\\ J(3)=3,I(3)=1& ⟹I(n)-J(n)=-2^m.\end{array}$$

That is to say

$$I(n)=\{\begin{array}{ll}J(n)+2^{m-1},& \text{if }0\le l<2^{m-1};\\ J(n)-2^m,& \text{if }{2}^{m-1}\le l<2^m.\end{array}$$

1.16

Express $g(n)$ in the form

$$g(n)=A(n)\alpha +B(n){\beta }_0+C(n){\beta }_1+D(n)\gamma .$$

Let $g(n)=1$, which implies $(\alpha ,{\beta }_0,{\beta }_1,\gamma )=(1,-2,-2,0)$. Then

$$\begin{array}{}\text{(1)}& A(n)-2B(n)-2C(n)=1.\end{array}$$

Let $g(n)=n$, which implies $(\alpha ,{\beta }_0,{\beta }_1,\gamma )=(1,0,1,-1)$. Then

$$\begin{array}{}\text{(2)}& A(n)+C(n)-D(n)=n.\end{array}$$

Let $(\alpha ,{\beta }_0,{\beta }_1,\gamma )=(1,-2,-2,0)$, which gives $g(n)=3^m$. Then (note we’re representing in terms of $n=2^m+l$)

$$\begin{array}{}\text{(3)}& A(n)=3^m.\end{array}$$

Let $(\alpha ,{\beta }_0,{\beta }_1,\gamma )=(0,0,1,0)$. Similar to the binary expansion in the Josephus problem, we have

$$\begin{array}{}\text{(4)}& C(n)=(b_{m-1}\dots b_0{)}_3.\end{array}$$

I also checked that for $(1)(2)(3)$ and $(4)$,

$$\left|\begin{array}{cccc}1& -2& -2& 0\\ 1& 0& 1& -1\\ 1& 0& 0& 0\\ 0& 0& 1& 0\end{array}\right|\ne 0.$$

The recurrence is solvable; hence

$$\begin{array}{rl}A(n)& =3^m;\\ B(n)& =(3^m-2(b_{m-1}\dots b_0{)}_3-1)/2;\\ C(n)& =(b_{m-1}\dots b_0{)}_3;\\ D(n)& =3^m+(b_{m-1}\dots b_0{)}_3-n.\end{array}$$

Then

$$\begin{array}{rl}g(n)& =3^m\alpha +(3^m-2(b_{m-1}\dots b_0{)}_3-1)\frac{{\beta }_0}{2}+(b_{m-1}\dots b_0{)}_3{\beta }_1+(3^m+(b_{m-1}\dots b_0{)}_3-n)\gamma \\ & =(\alpha +\frac{{\beta }_0}{2}+\gamma )3^m+(-{\beta }_0+{\beta }_1+\gamma )(b_{m-1}\dots b_0{)}_3-\frac{{\beta }_0}{2}-n\gamma .\end{array}$$