Stars and bars through recursion.

Problem: You are given a recursive relation \[ F(n,m)=\sum_{k=1}^n F(k,m-1) \tag{A} \] where $F(n,1)=n$. Show that \[ F(n,m)=\binom{m+n-1}{n-1}. \]

Solution: Start by expanding the sum in $\text{(A})$: \[ F(n,m)=\sum_{k_1=1}^n \sum_{k_2=1}^{k_1} \cdots \sum_{k_{m-2}=1}^{k_{m-3}}\sum_{k_{m-1}=1}^{k_{m-2}} F(k_{m-1},1). \] Since $F(k_{m-1},1)=k_{m-1}$, \[ \sum_{k_{m-1}=1}^{k_{m-2}} F(k_{m-1},1)= \sum_{k_{m-1}=1}^{k_{m-2}} k_{m-1}=\frac{k_{m-2}(k_{m-2}+1)}{2} =\binom{k_{m-2}+1}{k_{m-2}-1}. \] The next sum is \[ \sum_{k_{m-2}=1}^{k_{m-3}}\binom{k_{m-2}+1}{k_{m-2}-1}; \] to evaluate this we will use the Egorychev method. Start with the first binomial coefficient integral \[ \binom{n}{k}=\frac{1}{2\pi i} \int_{\abs{z}=\varepsilon} \frac{(1+z)^n}{z^{k+1}} dz \] to write (replacing $k_{m-2}$ with $k$ and $k_{m-3}$ with $m$ for brevity) \[ \sum_{k=1}^{m}\binom{k+1}{k-1} = \sum_{k=1}^{m} \frac{1}{2\pi i} \int_{\abs{z}=\varepsilon} \frac{(1+z)^{k+1}}{z^k} dz. \] We have the expression \[ \sum_{k=1}^{m} \qty(\frac{1+z}{z})^k \] which is the sum of a geometric series and is equal to \[ \frac{\qty(\frac{1+z}{z})^{m+1}-1}{\frac{1+z}{z}-1} =z \qty(\qty(\frac{1+z}{z})^{m+1}-1). \] There are two integrals to evaluate: \[ I_1 = \frac{1}{2\pi i} \int_{\abs{z}=\varepsilon} z(1+z)\qty(\frac{1+z}{z})^{m+1} dz \] and \[ I_2= \frac{1}{2\pi i} \int_{\abs{z}=\varepsilon} z(1+z)dz. \] $I_2=0$; $I_1$ can be split into \[ \frac{1}{2\pi i} \int_{\abs{z}=\varepsilon} z^2 \qty(\frac{1+z}{z})^{m+1} dz \] and \[ \frac{1}{2\pi i} \int_{\abs{z}=\varepsilon} z \qty(\frac{1+z}{z})^{m+1} dz. \] Using the binomial expansion \[ (1+z)^{m+1}=\sum_{r=0}^{m+1} \binom{m+1}{r} z^r \] we have \[ \frac{1}{2\pi i} \int_{\abs{z}=\varepsilon} z^2 \qty(\frac{1+z}{z})^{m+1} dz = \frac{1}{2\pi i} \int_{\abs{z}=\varepsilon} z^{1-m} \sum_{r=0}^{m+1} \binom{m+1}{r} z^r dz \] and \[ \frac{1}{2\pi i} \int_{\abs{z}=\varepsilon} z \qty(\frac{1+z}{z})^{m+1} dz = \frac{1}{2\pi i} \int_{\abs{z}=\varepsilon} z^{-m} \sum_{r=0}^{m+1} \binom{m+1}{r} z^r dz. \] $1-m+r=-1$ when $r=m-2$ so the residue from the first integral is \[ \binom{m+1}{m-2}; \] $r-m=-1$ when $r=m-1$ so the residue from the second integral is \[ \binom{m+1}{m-1}. \] One property of the binomial coefficient is that \[ \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1} \] and so \[ \binom{m+1}{m-2}+\binom{m+1}{m-1}=\binom{m+2}{m-1} \] or using the original notation \[ \binom{k_{m-3}+2}{k_{m-3}-1}. \] The next sum is \[ \sum_{k_{m-3}=1}^{k_{m-4}} \binom{k_{m-3}+2}{k_{m-3}-1} \] which using the same procedure evaluates to \[ \binom{k_{m-4}+3}{k_{m-4}-1}. \] The pattern we have established is that \[ \sum_{k=1}^n \binom{k+m}{k-1} =\binom{n+m+1}{n-1}. \] Following this process we eventually get to the sum \[ \sum_{k_1=1}^n \binom{k_1+m-2}{k_1-1} = \binom{m+n-1}{n-1}. \]

Comments

Post a Comment

Popular posts from this blog

CSAT 1

Image
Test Section A 1. You have a card of 10cm by 10cm. What is the largest volume in cm 3 of a box (without a lid) that can be obtained by cutting out a square of side x from each corner and then folding the flaps up? We can obtain an idea of the solution by looking at the following diagram: The box will have a base (marked in red on the diagram) with area $(l-2x)^2$ and height $x$. Therefore the volume of this box will be \begin{equation*} V=(l-2x)^x. \end{equation*} To maximize the volume first calculate \[ \dv{V}{x}=-4(l-2x)x+(l-2x)^2 \] using the product rule $d(u\cdot v)=du \cdot v + u \cdot dv$. Solve for $\dv*{V}{x}=0$ to find a (potential) maximum. If we assume that $x\neq l$ (a reasonable assumption since $x=l/2$ creates a nothing box) then \begin{align*} -4(l-2x)x+(l-2x)^2& =0 \\ l-2x-4x & = 0 \\ x & = \frac{l}{6}. \end{align*} To check that this is i...
Read more

Poor man's Daletskii-Krein

Image
Consider a second-order, symmetric tensor $A$ whose components $\def\R{\mathbb{R}}{A^j}_i \in \R$. We know that such a tensor has an eigen decomposition \begin{equation} \label{eigendecomp} A = V \Lambda V^\top \end{equation} where $V$ is an orthonormal, second-order tensor and ${\Lambda^j}_i=\lambda^j \delta^j_i$ ($\lambda^i$ is the $i$th eigenvalue of $A$). One corollary of (\ref{eigendecomp}) is \begin{equation} \label{An} A^n = V \Lambda^n V^\top . \end{equation} A function $f:\R \to \R$ that is analytic at $x=0$ is equal to its Maclaurin series \begin{equation} \label{maclaurin} f(x) = \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!} x^n \end{equation} where $f^{(0)}(0)=f(0)$ and $f^{(n)}(0)=\eval{\dv[n]{f}{x}}_{x=0}$. If we define \begin{equation} \label{def-fA} f(A):= \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!} A^n \end{equation} then $f(A)$ is also a second-order, sy...
Read more

PAT 2022

Image
1. What is the total resistance of the circuit ? 2. For which values of $x$ is $\qty(24-14x -3x^2)^{-1}$ positive? The $-1$ exponent does not change the sign. We can factorise $24-14x -3x^2$ as $(-3x+4)(x+6)$ which is positive either if $x < \frac{4}{3}, x > -6$ or if $x > \frac{4}{3}$, $x < -6$. The second condition cannot hold so we have to go with (D). 3. Molecules of oxygen in the atmosphere absorb solar radiation in bands centred at about 80 nm, 650 nm and 1000 nm. In which parts of the electromagnetic spectrum are these absorption bands? Picture from tikz.net The visible spectrum is in the very narrow band from 380 nm (violet) to 750 nm (red) so 650 nm is in the visible spectrum in the red zone. $1000 \ {\rm nm}=10^{-6} \ {\rm m}$ which is right at the edge of infrared. Finally $80 \ {\rm nm}= 0...
Read more