I encountered to following textbook problem in the book 'Introduction to probability' (p.34) by Blitzstein and Nwang.

  • NO homework, but self-study !

enter image description here

Part a) is no problem, but b) struck me down. First, I don't get it how you obtain the last expression on the right hand side by squaring (n+1) over k. Second, I have no idea how their hint should be used to solve the problem

Any help is appreciated!


We’re going to count the sequences of $4$ numbers from the set $\{0,1,\ldots,n\}$ that have the property that the first three numbers in the sequence are all less than the fourth. This means that the fourth number must be from the set $\{1,\ldots,n\}$: it can’t be $0$. Say that the fourth number is $k$. The other three numbers must come from the set $\{0,\ldots,k-1\}$ has $k$ elements, so they can be chosen in $k^3$ different ways, since we allow repetitions. Thus, for each $k\in\{1,\ldots,n\}$ there are $k^3$ sequences of the desired type with last term $k$, and there are therefore $1^3+2^3+\ldots+n^3$ sequences of the desired type.

Call this set of sequences $S$. Now we’ll count the members of $S$ according to the number of different numbers in the sequence. Say the sequence is $\langle a_1,a_2,a_3,a_4\rangle$. We know that $a_1,a_2,a_3<a_4$, so even if the first three terms are all equal, there are at least $2$ and at most $4$ different numbers in the sequence. How many such sequences are there with exactly $2$ different numbers? They’re easy to count: pick any two numbers from $\{0,\ldots,n\}$, make the larger one $a_4$, and set $a_1,a_2$, and $a_3$ equal to the smaller one. This produces a sequence in $S$, and every sequence in $S$ with exactly $2$ different numbers can be formed uniquely in this way, so there are $\binom{n+1}2$ such sequences, one for every pair of integers from the set $\{0,\ldots,n\}$.

To form a sequence with $3$ different members, we choose $3$ elements from $\{0,\ldots,n\}$. The largest will of course be $a_4$. However, there are $6$ ways to distribute the other $2$ among $a_1,a_2$, and $a_3$. Say the two smaller numbers are $k$ and $\ell$. There are $3$ ways to choose one of $a_1,a_2$, and $a_3$ to be the singleton and $2$ ways to decide whether it will be $k$ or $\ell$; once one of those $3\cdot2=6$ choices has been made, the other two of $a_1,a_2$, and $a_3$ will of course be the other one of $k$ and $\ell$, so the entire sequence is determined. There are $\binom{n+1}3$ ways to choose the $3$ numbers, and for each choice of $3$ numbers $6$ ways to assign them to form a member of $S$, so there are $6\binom{n+1}3$ members of $S$ with exactly $3$ different terms.

Finally, there are $\binom{n+1}4$ ways to choose $4$ distinct members of $\{0,\ldots,n\}$. The largest will be $a_4$, but the other $3$ can be assigned to $a_1,a_2$, and $a_3$ in $3!=6$ different ways, so there are $6\binom{n+1}4$ members of $S$ with $4$ distinct terms. Putting the results together, we see that


The rest is algebra:

$$\begin{align*} 6\binom{n+1}4&+6\binom{n+1}3+\binom{n+1}2\\\\ &=\frac{6(n+1)n(n-1)(n-2)}{4!}+\frac{6(n+1)n(n-1)}{3!}+\frac{n(n+1)}2\\\\ &=\frac{n(n+1)}2\left(\frac{(n-1)(n-2)}2+2(n-1)+1\right)\\\\ &=\frac{n(n+1)}2\cdot\frac{n^2+n}2\\\\ &=\binom{n+1}2^2\;. \end{align*}$$

  • $\begingroup$ This is an excellent and elaborate solution to the problem, much appreciated. A single question remains: Is there any strategy to come up with that kind of story without the hint in the exercise? The connecting bridge is the two different ways of counting the number of seqences with the first three numbers less than the fourth. How do you work it out to consider THIS scenario? $\endgroup$ Dec 5 '14 at 20:10
  • $\begingroup$ @Dominik: A lot of it is experience. After you’ve seen enough of these combinatorial arguments, you recognize some recurring themes. When one side is a sum over some range of integers, trying to find a way to make each term of the sum count some part of the set related to the value of the index of that term is a fairly natural idea, but experience is very helpful in coming up with scenarios to try. Part of it is asking oneself what sort of thing the various parts of an expression might be counting. $\endgroup$ Dec 5 '14 at 20:16
  • $\begingroup$ In see, with experience, someone would look at the left hand side and intuitively grasp the first part of the story: We have cubes, so the story has to contain the choice of three elements with replacement, and we have bases from 1 to n, which makes up the part of the fourth number being bigger. Am I right assuming that one would make up a different second part of the story (splitting the set S in a different way) one could easily generate a new right hand side expression? $\endgroup$ Dec 5 '14 at 20:32
  • $\begingroup$ @Dominik: If one came up with another story, one could use it to get a different righthand side, provided that it split $S$ up into pieces whose sizes could be calculated. Sometimes one comes up with what looks like a promising story but finds that the pieces aren’t easy to work with. Sometimes the opposite happens: one has a righthand side that seems to correspond nicely to counting certain things, but one can’t find a story that makes those things correspond to what one has done on the other side. $\endgroup$ Dec 5 '14 at 20:37
  • $\begingroup$ With this problem, I really learned something. Initially when I first read the hint, I was distracted by trying to figure out the WHY I should do it like that, instead of focussing on simply doing it. Probably something to be learned when studying such problems. $\endgroup$ Dec 5 '14 at 20:48

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{#c00000}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ We can write $\ds{\sum_{k\ =\ 0}^{n}k^{3}}$ as a polynomial in $\ds{n}$:

\begin{equation} \sum_{k\ =\ 0}^{n}k^{3}=\overbrace{a_{0}}^{\ds{=\ \color{#c00000}{0}}} + a_{1}n + a_{2}n^{2} + a_{3}n^{3} + a_{4}n^{4}\,,\qquad \forall\ n \in {\mathbb N}\tag{1} \end{equation} Why is it so ?. Any coefficient beyond $\ds{n = 4}$ vanishes out because $\ds{\pars{~\mbox{with}\ m \in {\mathbb N}_{+}~}}$ $$ \lim_{n\ \to\ \infty}{1 \over n^{m}}\sum_{k\ =\ 0}^{n}k^{3} =\lim_{n\ \to\ \infty}{\pars{n + 1}^{3} \over \pars{n + 1}^{m} - n^{m}} =\left\{\begin{array}{lcl} \infty & \mbox{if} & 1 \leq m \leq 3 \\[2mm] {1 \over 4} & \mbox{if} & m = 4 \\[2mm] 0 & \mbox{if} & m \geq 5 \end{array}\right. $$

From $\pars{1}$ we get: \begin{align}\color{#66f}{\large a_{4}}&=\lim_{n\ \to\ \infty}{1 \over n^{4}}\sum_{k\ =\ 0}^{n}k^{3} = \color{#66f}{\large{1 \over 4}} \quad\imp\quad \sum_{k\ =\ 0}^{n}k^{3} - {1 \over 4}\, n^{4}=a_{1}n + a_{2}n^{2} + a_{3}n^{3} \end{align}

Then \begin{align} \color{#66f}{\large a_{3}}&=\lim_{n\ \to\ \infty}{\sum_{k\ =\ 0}^{n}k^{3} - n^{4}/4 \over n^{3}} =\lim_{n\ \to\ \infty}{\pars{n + 1}^{3} - \pars{n + 1}^{4}/4 + n^{4}/4 \over \pars{n + 1}^{3} - n^{3}} =\color{#66f}{\large\half} \end{align}

Similarly, \begin{align} \color{#66f}{\large a_{2}}& =\lim_{n\ \to\ \infty}{\sum_{k\ =\ 0}^{n}k^{3} - n^{4}/4 - n^{3}/2 \over n^{2}} =\color{#66f}{\large{1 \over 4}} \\[5mm] \color{#66f}{\large a_{1}}& =\lim_{n\ \to\ \infty}{\sum_{k\ =\ 0}^{n}k^{3} - n^{4}/4 - n^{3}/2 - n^{2}/4 \over n} =\color{#66f}{\large 0} \end{align}

Then $$ \color{#66f}{\large\sum_{k\ =\ 0}^{n}\!\!k^{3}} ={1 \over 4}\,n^{2} + \half\,n^{3} + {1 \over 4}\,n^{4} ={n^{2}\pars{n^{2} + 2n + 1} \over 4} ={n^{2}\pars{n + 1}^{2} \over 4} =\color{#66f}{\large\bracks{n\pars{n + 1} \over 2}^{2}} $$

  • 1
    $\begingroup$ I'm afraid this is the solution to a different problem. $\endgroup$ Dec 5 '14 at 20:12
  • $\begingroup$ @Dominik Yes. It's true. I just misread the original statement. I'll delete this within one day such that you can read this comment. Sorry. Thanks. $\endgroup$ Dec 5 '14 at 20:44
  • $\begingroup$ @Dominik I just changed my previous answer. $\endgroup$ Dec 6 '14 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.