Recent questions tagged binomial-theorem

1
Determine a formula involving binomial coefficients for the nth term of a sequence if its initial terms are those listed. [Hint: Looking at Pascal's triangle will be helpful. Although infinitely many sequences start with a specified set of terms, each of the following lists is the start of a sequence of ... $1, 3, 15, 84, 495, 3003, 18564, 116280, 735471, 4686825,\dots$
2
Give a combinatorial proof that if n is a positive integer then $\displaystyle\sum_{k = 0}^{n} k^{2} \binom{n} {k} = n(n + 1)2^{n−2}.$ [Hint: Show that both sides count the ways to select a subset of a set of $n$ elements together with two not necessarily distinct elements from this subset. Furthermore, express the right-hand side as $n(n − 1)2^{n−2} + n2^{n−1}.]$
3
Use question $33$ to prove the hockeystick identity from question $27.$ [Hint: First, note that the number of paths from $(0, 0)\: \text{to}\: (n + 1,r)$ equals $\binom{n + 1 + r}{r}.$ Second, count the number of paths by summing the number of these paths that start by going $k$ units upward for $k = 0, 1, 2,\dots,r.]$
4
Use question $33$ to prove Pascal’s identity. [Hint: Show that a path of the type described in question $33$ from $(0, 0)\: \text{to}\: (n + 1 − k, k)$ passes through either $(n + 1 − k, k − 1)\: \text{or} \:(n − k, k),$ but not through both.]
5
Use question $33$ to prove Theorem $4.$ [Hint: Count the number of paths with n steps of the type described in question $33.$ Every such path must end at one of the points $(n − k, k)\:\text{for}\: k = 0, 1, 2,\dots,n.]$
6
Use question $33$ to give an alternative proof of Corollary $2$ in Section $6.3,$ which states that $\binom{n}{k} = \binom{n}{n−k}$ whenever $k$ is an integer with $0 \leq k \leq n.[$Hint: Consider the number of paths of the type described in question $33$ from $(0, 0)\: \text{to}\: (n − k, k)$ and from $(0, 0)\: \text{to}\:(k, n − k).]$
7
In this exercise we will count the number of paths in the $xy$ plane between the origin $(0, 0)$ and point $(m, n),$ where $m$ and $n$ are nonnegative integers, such that each path is made up of a series of steps, where each step is a move one unit to the right or ... and a $1$ represents a move one unit upward. Conclude from part $(A)$ that there are $\binom{m + n}{n}$ paths of the desired type.
8
Prove the binomial theorem using mathematical induction.
9
Show that a nonempty set has the same number of subsets with an odd number of elements as it does subsets with an even number of elements.
10
Give a combinatorial proof that $\displaystyle{}\sum_{k = 1}^{n} k \binom{n}{k}^{2} = n \binom{2n−1}{n−1}.$ [Hint: Count in two ways the number of ways to select a committee, with $n$ members from a group of $n$ mathematics professors and $n$ computer science professors, such that the chairperson of the committee is a mathematics professor.]
11
Give a combinatorial proof that $\displaystyle{}\sum_{k = 1}^{n} k \binom{n}{k} = n2^{n−1}.$ [Hint: Count in two ways the number of ways to select a committee and to then select a leader of the committee.]
12
Show that if $n$ is a positive integer, then $\binom{2n}{2} = 2\binom{n}{2} + n^{2}$ using a combinatorial argument. by algebraic manipulation.
13
Prove the hockeystick identity $\displaystyle{}\sum_{k=0}^{r} \binom{n + k}{k} = \binom{n + r + 1}{r}$ whenever $n$ and $r$ are positive integers, using a combinatorial argument. using Pascal’s identity.
14
Let $n$ and $k$ be integers with $1 \leq k \leq n.$ Show that $\displaystyle{}\sum_{k=1}^{n} \binom{n}{k}\binom{n}{k − 1} = \dfrac{\binom{2n + 2}{n + 1}}{2} − \binom{2n}{n}.$
15
Let n be a positive integer. Show that $\binom{2n}{n + 1} + \binom{2n}{n} = \dfrac{\binom{2n + 2}{n + 1}}{2}.$
16
Show that if $p$ is a prime and $k$ is an integer such that $1 \leq k \leq p − 1,$ then $p$ divides $\binom{p}{k} .$
17
Show that if $n$ and $k$ are positive integers, then $\binom{n + 1}{k} = \dfrac{(n + 1)\binom {n}{k – 1}}{k}.$ Use this identity to construct an inductive definition of the binomial coefficients.
18
Prove the identity $\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n−k}{r−k} ,$ whenever $n, r,$ and $k$ are nonnegative integers with $r \leq n$ and $k \leq r,$ using a combinatorial argument. using an argument based on the formula for the number of $r$-combinations of a set with $n$ elements.
19
Prove that if $n$ and $k$ are integers with $1 \leq k \leq n,$ then $k \binom{n}{k} = n \binom{n−1}{k−1},$ using a combinatorial proof. [Hint: Show that the two sides of the identity count the number of ways to select a subset with $k$ elements from a set ... then an element of this subset.] using an algebraic proof based on the formula for $\binom{n}{r}$ given in Theorem $2$ in Section $6.3.$
20
Suppose that $k$ and $n$ are integers with $1 \leq k<n.$ Prove the hexagon identity $\binom{n-1}{k-1}\binom{n}{k+1}\binom{n+1}{k} = \binom{n-1}{k}\binom{n}{k-1}\binom{n+1}{k+1},$ which relates terms in Pascal’s triangle that form a hexagon.
21
Prove Pascal’s identity, using the formula for $\binom{n}{r}.$
22
Suppose that $b$ is an integer with $b \geq 7.$ Use the binomial theorem and the appropriate row of Pascal’s triangle to find the base-$b$ expansion of $(11)^{4}_{b}$ [that is, the fourth power of the number $(11)_{b}$ in base-$b$ notation].
23
Show that if $n$ and $k$ are integers with $1 \leq k \leq n,$ then $\binom{n}{k} \leq \frac{n^{k}}{2^{k−1}}.$
24
Use question $14$ and Corollary $1$ to show that if $n$ is an integer greater than $1,$ then $\binom{n}{\left \lfloor n/2 \right \rfloor}\geq \frac{2^{n}}{2}.$ Conclude from part $(A)$ that if $n$ is a positive integer, then $\binom{2n}{n}\geq \frac{4^{n}}{2n}.$
25
Show that $\binom{n}{k} \leq 2^{n}$ for all positive integers $n$ and all integers $k$ with $0 \leq k \leq n.$
26
Show that if $n$ is a positive integer, then $1 = \binom{n}{0}<\binom{n}{1}<\dots < \binom{n}{\left \lfloor n/2 \right \rfloor} = \binom{n}{\left \lceil n/2 \right \rceil}>\dots \binom{n}{n-1}>\binom{n}{n}=1.$
27
What is the row of Pascal’s triangle containing the binomial coefficients $\binom{9}{k} ,\: 0 \leq k \leq 9?$
The row of Pascal’s triangle containing the binomial coefficients $\binom{10}{k},\: 0 \leq k \leq 10, \:\text{is:}\: 1\:\: 10\:\: 45\:\: 120\:\: 210\:\: 252\:\: 210\:\: 120\:\: 45\:\: 10\:\: 1$ Use Pascal’s identity to produce the row immediately following this row in Pascal’s triangle.
Give a formula for the coefficient of $x^{k}$ in the expansion of $\left(x^{2} − \frac{1}{x}\right)^{100},$ where $k$ is an integer.
Give a formula for the coefficient of $x^{k}$ in the expansion of $\left(x + \frac{1}{x}\right)^{100},$ where $k$ is an integer.