Concrete Mathematics Chapter one note

Chapter 1 Recurrent problem

For Hanoi problem, consider the largest disk must be moved when the \(n-1\) disks on it were moved. And once \(T_{n-1}\) times are down, we must at least move the largest one once and do another \(T_{n-1}\) times to make it. Hence: \[ T_{n}\geq2T_{n-1}+1 \] Apparently we can give a structure to suit this \(T_n\) , so recurrence \(T_n=2T_{n-1}+1\), then \(T_n=2^n-1\)

For Lines-in-the-plane problem, consider nth line can intersect \(n-1\) common points, and these points divide this line into \(n\) parts, each part gives one more region. Hence: \[ L_n\leq L_{n-1}+n \] Combined with boundary value, so \(L_n=\dfrac{n(n+1)}{2}+1\\\)

For Zigs-in-the-plane problem, if extend the sharp side, we have \(Z'_{n}=L_{2n}=2n^2+n+1\), but because of the sharps, the ideal situation is each sharp lose two regions. So \(Z_n=Z'_{n}-2\cdot n=2n^2-n+1\)

For Josephus problem, assume the order of the death is \(2\). Consider \(1,2,\dots ,2n\), after first round the circle leave \(1,3,\cdots ,2n-1\), and each correspond to the n-people situation, hence: \[ J_{2n}=2J_{n}-1 \] This equation gives that \(J_{2^n}\equiv1\), when the number of people is the power of \(2\), the first guy is lucky. And consider \(1,2,\cdots ,2n,2n+1\), after first round it remains \(3,5,\cdots ,2n+1\), each correspond to the n-people situation, hence:

\[ J_{2n+1}=2J_{n}+1 \] And define \(m\triangleq \lfloor log_2 n\rfloor\) , so \(l\triangleq n-2^m\in[0,\dfrac{n}{2})\), and after \(l\) times the number is power of 2 and the first guy that is currently pointed is lucky. Hence: \[ J_{n}=2l+1=2(n-2^{\lfloor log_2 n \rfloor})+1 \]

long long BinarySolutionToJosephusTwo(long long a) {	//time complexity O(logn)
    long long A = a;
    while ((A & (A - 1)) != 0)	//get the first 1
        A &= (A - 1);	
    return ((a - A) << 1) + 1;
}

To generalize it, we assume that \(f(j)=\alpha_j(1\leq j<d)\) and \[ f(dn+j)=cf(n)+\beta_j(0\leq j \] Use base system, the result is: \[ f((b_mb_{m-1}\cdots b_1b_0)_d)=(\alpha_{b_m}\beta_{b_{m-1}}\beta_{b_{m-2}}\cdots \beta_{b_1}\beta_{b_0})_c \] Beautiful proof of AGM(Arithmetic-Geometric-Mean inequality), let \(P(n)\) means when there are n numbers is true: \[ P(2)\ is\ true ,P(n)\to P(n-1),P(n)\ and \ P(2)\to P(2n) \] repertoire method: Use undetermined function method to solve recurrent problem, for instance \[ \begin{aligned} &R_{0}=\alpha \\ &R_{n}=2R_{n-1}+\beta n+\gamma \end{aligned} \] Set \(R_{n}=A(n) \alpha+B(n) \beta+C(n) \gamma\), use some special situations to get \(A(n),B(n),C(n)\) \[ \begin{cases} R_{n}=1\Longrightarrow \alpha=1,\gamma=-1,\beta=0\Longrightarrow A(n)-C(n)=1\\ R_{n}=n\Longrightarrow \alpha=0,n=2\cdot (n-1)+\beta n+\gamma,\beta=-1,\gamma=2\Longrightarrow2C(n)-B(n)=n\\ R_{n}=2^n\Longrightarrow \alpha=1,2^n=2\cdot 2^{n-1}+\beta n+\gamma\Longrightarrow\beta=\gamma=0\Longrightarrow A(n)=2^{n} \end{cases} \] Solution \(\begin{cases}A(n)=2^n\\B(n)=2^{n+1}-n-2\\C(n)=2^{n}-1\end{cases}\), then \(R_{n}=(\alpha+2\beta+\gamma)2^{n}-\beta n-(2\beta+\gamma)\)

\(n\) planes divide the three dimensions space into \(\large C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+C_{n}^{3}\) pieces at most.

consider \(T_{n}\) and \(T_{n-1}\), the pieces that are added is \(n-1\) lines that cut the new plane, so that \[ T_{n}=T_{n-1}+\large C_{n-1}^{0}+C_{n-1}^{1}+C_{n-1}^{2} \] So we can guess that when the super-plane is \(d-1\) dimensions, then \(n\) super-planes cut the \(d\) dimensions space into \(\displaystyle \sum_{k=0}^{d}\large C_{n}^{i}\) pieces at most.