Discrete Math Problems: VIII Principle of Mathematical Induction
Principle of Mathematical Induction
- Triangular Numbers (Sum of First \(n\) Positive Integers):
\[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \]
Base Case: Let \(n=1\). Then $ 1 = \frac{1(1+1)}{2}. $ Since $ \frac{2}{2} = 1, $ the statement holds for \(n=1\).
Inductive Step: Assume that for some \(n \ge 1\), $ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}. $ We must show that $ 1 + 2 + 3 + \cdots + n + (n+1) = \frac{(n+1)(n+2)}{2}. $
Starting from the left-hand side: $ 1 + 2 + 3 + \cdots + n + (n+1) $
Using the inductive hypothesis, substitute: $ \frac{n(n+1)}{2} + (n+1). $
Factor: $ (n+1)\left(\frac{n}{2} + 1\right) = (n+1)\left(\frac{n+2}{2}\right). $
Thus, $ = \frac{(n+1)(n+2)}{2}. $
Hence the statement holds for \(n+1\). By mathematical induction, the formula holds for all \(n \ge 1\).
- Sum of Odd Numbers:
\[ 1 + 3 + 5 + \cdots + (2n-1) = n^2 \]
Base Case: Let \(n=1\). Then $ 1 = 1^2. $ Since $ 1 = 1, $ the statement holds for \(n=1\).
Inductive Step: Assume that for some \(n \ge 1\), $ 1 + 3 + 5 + \cdots + (2n-1) = n^2. $ We must show that $ 1 + 3 + 5 + \cdots + (2n-1) + (2(n+1)-1) = (n+1)^2. $
Starting from the left-hand side: $ 1 + 3 + 5 + \cdots + (2n-1) + (2(n+1)-1) $
Using the inductive hypothesis, substitute: $ n^2 + (2(n+1)-1). $
Simplify: $ n^2 + 2n + 1. $
Factor: $ = (n+1)^2. $
Hence the statement holds for \(n+1\). By mathematical induction, the formula holds for all \(n \ge 1\).
- Sum of First \(n\) Square Numbers
\[ 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} \]
Base Case: Let \(n=1\). Then $ 1^2 = \frac{1(1+1)(2(1)+1)}{6}. $ Since $ \frac{1 \cdot 2 \cdot 3}{6} = 1, $ the statement holds for \(n=1\).
Inductive Step: Assume that for some \(n \ge 1\), $ 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}. $ We must show that $ 1^2 + 2^2 + 3^2 + \cdots + n^2 + (n+1)^2 = \frac{(n+1)(n+2)(2n+3)}{6}. $
Starting from the left-hand side: $ 1^2 + 2^2 + 3^2 + \cdots + n^2 + (n+1)^2 $
Using the inductive hypothesis, substitute: $ \frac{n(n+1)(2n+1)}{6} + (n+1)^2. $
Factor: $ (n+1)\left(\frac{n(2n+1)}{6} + (n+1)\right). $
Combine terms: $ (n+1)\left(\frac{2n^2+n+6n+6}{6}\right) = (n+1)\left(\frac{2n^2+7n+6}{6}\right). $
Factor the quadratic: $ (n+1)\left(\frac{(2n+3)(n+2)}{6}\right). $
Thus, $ = \frac{(n+1)(n+2)(2n+3)}{6}. $
Hence the statement holds for \(n+1\). By mathematical induction, the formula holds for all \(n \ge 1\).
- Tetrahedral Numbers (Sum of First $n$ Triangular Numbers):
\[ 1 + 3 + 6 + 10 + \cdots + \frac{n(n+1)}{2} = \frac{n(n+1)(n+2)}{6} \]
Base Case: Let \(n=1\). Then $ 1 = \frac{1(1+1)(1+2)}{6}. $ Since $ \frac{1 \cdot 2 \cdot 3}{6} = 1, $ the statement holds for \(n=1\).
Inductive Step: Assume that for some \(n \ge 1\), $ 1 + 3 + 6 + 10 + \cdots + \frac{n(n+1)}{2} = \frac{n(n+1)(n+2)}{6}. $ We must show that $ 1 + 3 + 6 + 10 + \cdots + \frac{n(n+1)}{2} + \frac{(n+1)(n+2)}{2} = \frac{(n+1)(n+2)(n+3)}{6}. $
Starting from the left-hand side: $ 1 + 3 + 6 + 10 + \cdots + \frac{n(n+1)}{2} + \frac{(n+1)(n+2)}{2} $
Using the inductive hypothesis, substitute: $ \frac{n(n+1)(n+2)}{6} + \frac{(n+1)(n+2)}{2}. $
Factor: $ (n+1)(n+2)\left(\frac{n}{6} + \frac{1}{2}\right). $
Combine terms: $ (n+1)(n+2)\left(\frac{n+3}{6}\right). $
Thus, $ = \frac{(n+1)(n+2)(n+3)}{6}. $
Hence the statement holds for \(n+1\). By mathematical induction, the formula holds for all \(n \ge 1\).
- Sum of First $n$ Cube Numbers:
\[ 1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]
Base Case: Let \(n=1\). Then $ 1^3 = \left(\frac{1(1+1)}{2}\right)^2. $ Since $ \left(\frac{2}{2}\right)^2 = 1, $ the statement holds for \(n=1\).
Inductive Step: Assume that for some \(n \ge 1\), $ 1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2. $ We must show that $ 1^3 + 2^3 + 3^3 + \cdots + n^3 + (n+1)^3 = \left(\frac{(n+1)(n+2)}{2}\right)^2. $
Starting from the left-hand side: $ 1^3 + 2^3 + 3^3 + \cdots + n^3 + (n+1)^3 $
Using the inductive hypothesis, substitute: $ \left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3. $
Factor out \((n+1)^2\): $ (n+1)^2\left(\frac{n^2}{4} + (n+1)\right). $
Combine terms: $ (n+1)^2\left(\frac{n^2 + 4n + 4}{4}\right). $
Factor the quadratic: $ (n+1)^2\left(\frac{(n+2)^2}{4}\right). $
Thus, $ = \left(\frac{(n+1)(n+2)}{2}\right)^2. $
Hence the statement holds for \(n+1\). By mathematical induction, the formula holds for all \(n \ge 1\).
- General Geometric Series Partial Sum Formula:
\[ \sum_{k=0}^{n-1} ar^k = \frac{a(1-r^n)}{1-r} \qquad \text{for } r \ne 1 \]
Base Case: Let \(n=1\). Then $ \sum_{k=0}^{0} ar^k = ar^0 = a. $ The formula gives $ \frac{a(1-r^1)}{1-r} = \frac{a(1-r)}{1-r} = a. $ Thus, the statement holds for \(n=1\).
Inductive Step: Assume that for some \(n \ge 1\), $ \sum_{k=0}^{n-1} ar^k = \frac{a(1-r^n)}{1-r}. $ We must show that $ \sum_{k=0}^{n} ar^k = \frac{a(1-r^{n+1})}{1-r}. $ Starting from the left-hand side, $ \sum_{k=0}^{n} ar^k = \left(\sum_{k=0}^{n-1} ar^k\right)+ar^n. $ Using the inductive hypothesis, substitute: $ \frac{a(1-r^n)}{1-r}+ar^n. $ Write both terms over a common denominator: $ \frac{a(1-r^n)}{1-r} + \frac{ar^n(1-r)}{1-r}. $ Combine the numerators: $ \frac{a(1-r^n)+ar^n-ar^{n+1}}{1-r}. $ Simplify: $ \frac{a-ar^{n+1}}{1-r}. $ Factor out \(a\): $ \frac{a(1-r^{n+1})}{1-r}. $ Thus, $ \sum_{k=0}^{n} ar^k = \frac{a(1-r^{n+1})}{1-r}. $ Hence the statement holds for \(n+1\). By mathematical induction, the formula holds for all \(n \ge 1\), provided \(r \ne 1\).
- Cardinality of the Power Set:
\[ |P(A)| = 2^{|A|} \]
Base Case: Let \(n=|A|=0\). Then \(A=\varnothing\). Its power set is $ P(\varnothing)=\{\varnothing\}. $ Hence $ |P(\varnothing)|=1. $ Since $ 2^0=1, $ we conclude $ |P(A)|=2^{|A|}. $
Inductive Step: Assume that for some \(n \ge 0\), every set \(A\) with \(|A|=n\) satisfies $ |P(A)| = 2^n. $ We must show that if \(|B|=n+1\), then $ |P(B)| = 2^{n+1}. $ Let \(B\) be a set with \(|B|=n+1\), and choose an element \(x \in B\). Write $ B = A \cup \{x\}, $ where \(|A|=n\). Every subset of \(B\) either contains \(x\) or does not contain \(x\).
(1) Subsets not containing \(x\): these are exactly the subsets of \(A\), so there are \(|P(A)|\) of them.
(2) Subsets containing \(x\): each is uniquely of the form \(S \cup \{x\}\), where \(S \subseteq A\), so there are again \(|P(A)|\) of them.Thus, $ |P(B)| = |P(A)| + |P(A)| = 2|P(A)|. $ By the inductive hypothesis, $ |P(B)| = 2 \cdot 2^n = 2^{n+1}. $ By the principle of mathematical induction, if \(|A|=n\), then $ |P(A)| = 2^n $ for all \(n \ge 0\).
- Pascal's Identity:
\[ \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1} \quad \text{for} \quad 1 \leq k \leq n \]
Base Case: Let \(n=k\). Then $ \binom{k+1}{k}=k+1, $ and $ \binom{k}{k}+\binom{k}{k-1}=1+k. $ Hence $ \binom{k+1}{k}=\binom{k}{k}+\binom{k}{k-1}. $
Inductive Step: Assume that for some \(n\ge k\), $ \binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}. $ We must show that $ \binom{n+2}{k}=\binom{n+1}{k}+\binom{n+1}{k-1}. $ Using the definition of binomial coefficients, $ \binom{n+1}{k}+\binom{n+1}{k-1} = \frac{(n+1)!}{k!(n-k+1)!} + \frac{(n+1)!}{(k-1)!(n-k+2)!}. $ Factoring out $ \frac{(n+1)!}{k!(n-k+2)!}, $ gives $ \frac{(n+1)!}{k!(n-k+2)!}\big((n-k+2)+k\big) = \frac{(n+1)!(n+2)}{k!(n-k+2)!} = \frac{(n+2)!}{k!(n+2-k)!} = \binom{n+2}{k}. $ Therefore, $ \binom{n+2}{k}=\binom{n+1}{k}+\binom{n+1}{k-1}. $
By the principle of mathematical induction, the identity holds for all \(n\ge k+1\).
- Hockey-Stick Identity:
\[ \sum_{k=r}^n \binom{k}{r} = \binom{n+1}{r+1} \quad \text{for} \quad 0 \leq r \leq n \]
Base Case: Let \(n=r\). Then $ \sum_{k=r}^{r}\binom{k}{r}=\binom{r}{r}=1, $ and $ \binom{r+1}{r+1}=1. $ Hence $ \sum_{k=r}^{r}\binom{k}{r}=\binom{r+1}{r+1}. $
Inductive Step: Assume that for some \(n\ge r\), $ \sum_{k=r}^{n}\binom{k}{r}=\binom{n+1}{r+1}. $ We must show that $ \sum_{k=r}^{n+1}\binom{k}{r}=\binom{n+2}{r+1}. $ Now, $ \sum_{k=r}^{n+1}\binom{k}{r} = \left(\sum_{k=r}^{n}\binom{k}{r}\right)+\binom{n+1}{r}. $ Using the inductive hypothesis, $ \sum_{k=r}^{n+1}\binom{k}{r} = \binom{n+1}{r+1}+\binom{n+1}{r}. $ By Pascal’s Identity, $ \binom{n+1}{r+1}+\binom{n+1}{r}=\binom{n+2}{r+1}. $ Therefore, $ \sum_{k=r}^{n+1}\binom{k}{r}=\binom{n+2}{r+1}. $
By the principle of mathematical induction, the identity holds for all \(n\ge r\).
- Sum of Binomial Coefficients:
\[ \sum_{k=0}^n \binom{n}{k} = 2^n \]
Base Case: Let \(n=0\). Then $ \sum_{k=0}^{0}\binom{0}{k}=\binom{0}{0}=1, $ and $ 2^0=1. $ Hence $ \sum_{k=0}^{0}\binom{0}{k}=2^0. $
Inductive Step: Assume that for some \(n\ge0\), $ \sum_{k=0}^{n}\binom{n}{k}=2^n. $ We must show that $ \sum_{k=0}^{n+1}\binom{n+1}{k}=2^{n+1}. $ Now, using Pascal’s Identity, $ \binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}. $ Therefore, $ \sum_{k=0}^{n+1}\binom{n+1}{k} = \sum_{k=0}^{n+1}\left(\binom{n}{k}+\binom{n}{k-1}\right). $ Splitting the sums, $ \sum_{k=0}^{n+1}\binom{n+1}{k} = \sum_{k=0}^{n+1}\binom{n}{k} + \sum_{k=0}^{n+1}\binom{n}{k-1}. $ Since terms outside the range are zero, $ \sum_{k=0}^{n+1}\binom{n+1}{k} = \sum_{k=0}^{n}\binom{n}{k} + \sum_{k=0}^{n}\binom{n}{k}. $ Thus, $ \sum_{k=0}^{n+1}\binom{n+1}{k} = 2\sum_{k=0}^{n}\binom{n}{k}. $ Using the inductive hypothesis, $ \sum_{k=0}^{n+1}\binom{n+1}{k} = 2(2^n)=2^{n+1}. $
By the principle of mathematical induction, the identity holds for all \(n\ge0\).
- Symmetry of Binomial Coefficients:
\[ \binom{n}{k} = \binom{n}{n-k} \quad \text{for} \quad 0 \leq k \leq n \]
Base Case: Let \(n=0\). Then $ \binom{0}{0}=\binom{0}{0}. $ Hence the statement holds for \(n=0\).
Inductive Step: Assume that for some \(n\ge0\), $ \binom{n}{k}=\binom{n}{n-k} $ for all \(0\le k\le n\). We must show that $ \binom{n+1}{k}=\binom{n+1}{(n+1)-k}. $ Now, using Pascal’s Identity, $ \binom{n+1}{k} = \binom{n}{k-1}+\binom{n}{k}. $ Using the inductive hypothesis, $ \binom{n}{k-1} = \binom{n}{n-k+1}, $ and $ \binom{n}{k} = \binom{n}{n-k}. $ Therefore, $ \binom{n+1}{k} = \binom{n}{n-k+1} + \binom{n}{n-k}. $ Applying Pascal’s Identity again, $ \binom{n}{n-k+1} + \binom{n}{n-k} = \binom{n+1}{n+1-k}. $ Hence, $ \binom{n+1}{k} = \binom{n+1}{(n+1)-k}. $
By the principle of mathematical induction, the identity holds for all \(n\ge0\).
- Central Binomial Coefficient Inequality:
\[ \binom{n}{k} \leq \binom{n}{\lfloor n/2 \rfloor} \quad \text{for} \quad 0 \leq k \leq n \]
Base Case: Let \(n=1\). Then $ \binom{1}{0}=1 $ and $ \binom{1}{1}=1. $ Hence the largest coefficient occurs at the center.
Inductive Step: Assume that for some \(n\ge1\), $ \binom{n}{0}\leq\binom{n}{1}\leq\cdots\leq\binom{n}{\lfloor n/2\rfloor}. $ We must show the statement holds for \(n+1\).
Case 1: \(n=2m\) is even. Then the inductive hypothesis gives $ \binom{2m}{0}\leq\binom{2m}{1}\leq\cdots\leq\binom{2m}{m}. $ Using Pascal’s Identity, $ \binom{2m+1}{k} = \binom{2m}{k-1}+\binom{2m}{k}. $ Now consider consecutive terms: $ \binom{2m+1}{k+1}-\binom{2m+1}{k}. $ Using Pascal’s Identity, $ \binom{2m+1}{k+1}-\binom{2m+1}{k} = \binom{2m}{k+1}-\binom{2m}{k-1}. $ For \(k\leq m-1\), $ \binom{2m}{k+1}\geq\binom{2m}{k-1} $ by the inductive hypothesis. Hence, $ \binom{2m+1}{k+1}\geq\binom{2m+1}{k}. $ Therefore the coefficients increase up to the center. By symmetry, $ \binom{2m+1}{k}=\binom{2m+1}{2m+1-k}, $ so the maximum coefficient occurs at the two central terms: $ \binom{2m+1}{m}=\binom{2m+1}{m+1} = \binom{2m+1}{\lfloor \frac{2m+1}{2} \rfloor} = \binom{n+1}{\lfloor \frac{n+1}{2} \rfloor}. $
Case 2: \(n=2m+1\) is odd. Then the inductive hypothesis gives $ \binom{2m+1}{0}\leq\binom{2m+1}{1}\leq\cdots\leq\binom{2m+1}{m}\leq\binom{2m+1}{m+1}. $ Using Pascal’s Identity, $ \binom{2m+2}{k} = \binom{2m+1}{k-1}+\binom{2m+1}{k}. $ Again, $ \binom{2m+2}{k+1}-\binom{2m+2}{k} = \binom{2m+1}{k+1}-\binom{2m+1}{k-1}. $ For \(k\leq m-1\), $ \binom{2m+1}{k+1}\geq\binom{2m+1}{k-1}. $ Hence, $ \binom{2m+2}{k+1}\geq\binom{2m+2}{k}. $ Therefore the coefficients increase up to the middle term. By symmetry, $ \binom{2m+2}{k}=\binom{2m+2}{2m+2-k}, $ so the maximum coefficient occurs at the central term $ \binom{2m+2}{m+1} = \binom{n+1}{\lfloor \frac{n+1}{2} \rfloor}. $
By the principle of mathematical induction, the maximum binomial coefficient in row \(n\) is the central binomial coefficient.
- Stirling Numbers of the First Kind Recurrence Relation:
$$ \left[ {n \atop k} \right] = (n-1)\left[ {n-1 \atop k} \right] + \left[ {n-1 \atop k-1} \right] \quad \text{for} \quad 1\le k\le n $$
Where $\left[ {n \atop k} \right]$ denotes the Stirling number of the first kind, which counts the number of permutations of \(n\) distinct elements having exactly \(k\) disjoint cycles.
Base Case: Let \(n=1\). Then $ \left[ {1 \atop 1} \right]=1. $ Also, $ 0\left[ {0 \atop 1} \right] + \left[ {0 \atop 0} \right] = 0\cdot0+1=1. $ Hence, $ \left[ {1 \atop 1} \right] = 0\left[ {0 \atop 1} \right] + \left[ {0 \atop 0} \right]. $ Thus the statement holds for \(n=1\).
Inductive Step: Assume that for some \(n\ge1\), $ \left[ {n \atop k} \right] = (n-1)\left[ {n-1 \atop k} \right] + \left[ {n-1 \atop k-1} \right] $ for all \(1\le k\le n\). We must show that $ \left[ {n+1 \atop k} \right] = n\left[ {n \atop k} \right] + \left[ {n \atop k-1} \right]. $ Consider permutations of the set $ \{1,2,\dots,n,n+1\} $ having exactly \(k\) disjoint cycles. If \(n+1\) forms a cycle by itself, then the remaining \(n\) elements must form a permutation with exactly \(k-1\) cycles. This can be done in $ \left[ {n \atop k-1} \right] $ ways. If \(n+1\) is not alone, first form a permutation of the remaining \(n\) elements having exactly \(k\) cycles. This can be done in $ \left[ {n \atop k} \right] $ ways. Then insert \(n+1\) into one of the existing cycles. Since there are \(n\) possible positions immediately after the \(n\) existing elements in cycle notation, this gives $ n\left[ {n \atop k} \right] $ ways. Therefore, $ \left[ {n+1 \atop k} \right] = n\left[ {n \atop k} \right] + \left[ {n \atop k-1} \right]. $
By the principle of mathematical induction, the recurrence relation holds for all \(n\ge1\).
- Sum of Stirling Numbers of the First Kind:
$$ \sum_{k=0}^{n} \left[ {n \atop k} \right] = n! $$
Base Case: Let \(n=1\). Then $ \sum_{k=0}^{1} \left[ {1 \atop k} \right] = \left[ {1 \atop 0} \right] + \left[ {1 \atop 1} \right] = 0+1 = 1 = 1!. $ Thus the statement holds for \(n=1\).
Inductive Step: Assume that for some \(n\ge1\), $ \sum_{k=0}^{n} \left[ {n \atop k} \right] = n!. $ We must show that $ \sum_{k=0}^{n+1} \left[ {n+1 \atop k} \right] = (n+1)!. $ Using the recurrence relation $ \left[ {n+1 \atop k} \right] = n\left[ {n \atop k} \right] + \left[ {n \atop k-1} \right], $ we have $ \sum_{k=0}^{n+1} \left[ {n+1 \atop k} \right] = \sum_{k=0}^{n+1} \left( n\left[ {n \atop k} \right] + \left[ {n \atop k-1} \right] \right). $ Distributing the summation gives $ = n \sum_{k=0}^{n+1} \left[ {n \atop k} \right] + \sum_{k=0}^{n+1} \left[ {n \atop k-1} \right]. $ Since $ \left[ {n \atop n+1} \right]=0 \quad \text{and} \quad \left[ {n \atop -1} \right]=0, $ this becomes $ = n \sum_{k=0}^{n} \left[ {n \atop k} \right] + \sum_{k=0}^{n} \left[ {n \atop k} \right]. $ Factoring gives $ = (n+1) \sum_{k=0}^{n} \left[ {n \atop k} \right]. $ Applying the inductive hypothesis, $ = (n+1)n! = (n+1)!. $ Therefore, $ \sum_{k=0}^{n+1} \left[ {n+1 \atop k} \right] = (n+1)!. $
By the principle of mathematical induction, $ \sum_{k=0}^{n} \left[ {n \atop k} \right] = n! $ for all \(n\ge1\).
- Stirling Numbers of the Second Kind Recurrence Relation:
$$ \left\{ {n \atop k} \right\} = k\left\{ {n-1 \atop k} \right\} + \left\{ {n-1 \atop k-1} \right\} \quad \text{for} \quad 1\le k\le n $$
Where $\left\{ {n \atop k} \right\}$ denotes the Stirling number of the second kind, which counts the number of ways to partition a set of \(n\) distinct elements into \(k\) nonempty, unlabeled subsets.
Base Case: Let \(n=1\). Then $ \left\{ {1 \atop 1} \right\}=1. $ Also, $ 1\left\{ {0 \atop 1} \right\} + \left\{ {0 \atop 0} \right\} = 1\cdot0+1=1. $ Hence, $ \left\{ {1 \atop 1} \right\} = 1\left\{ {0 \atop 1} \right\} + \left\{ {0 \atop 0} \right\}. $ Thus the statement holds for \(n=1\).
Inductive Step: Assume that for some \(n\ge1\), $ \left\{ {n \atop k} \right\} = k\left\{ {n-1 \atop k} \right\} + \left\{ {n-1 \atop k-1} \right\} $ for all \(1\le k\le n\). We must show that $ \left\{ {n+1 \atop k} \right\} = k\left\{ {n \atop k} \right\} + \left\{ {n \atop k-1} \right\}. $ Consider partitions of the set $ \{1,2,\dots,n,n+1\} $ into \(k\) nonempty subsets. If \(n+1\) forms a subset by itself, then the remaining \(n\) elements must be partitioned into \(k-1\) nonempty subsets. This can be done in $ \left\{ {n \atop k-1} \right\} $ ways. If \(n+1\) is not alone, first partition the remaining \(n\) elements into \(k\) nonempty subsets. This can be done in $ \left\{ {n \atop k} \right\} $ ways. Then place \(n+1\) into one of the \(k\) existing subsets, giving $ k\left\{ {n \atop k} \right\} $ ways. Therefore, $ \left\{ {n+1 \atop k} \right\} = k\left\{ {n \atop k} \right\} + \left\{ {n \atop k-1} \right\}. $
By the principle of mathematical induction, the recurrence relation holds for all \(n\ge1\).
- Bell Number Binomial Recurrence Relation:
$$ B_n = \sum_{k=0}^{n-1} \binom{n-1}{k}B_k \quad \text{for} \quad n \geq 1 $$
Where the \(n\)-th Bell number, denoted by \(B_n\), is the number of ways to partition a set of \(n\) distinct elements into nonempty subsets.
Base Case: Let \(n=1\). Then $ B_1=1. $ Also, $ \sum_{k=0}^{0} \binom{0}{k}B_k = \binom{0}{0}B_0 = 1\cdot1 =1. $ Hence, $ B_1 = \sum_{k=0}^{0} \binom{0}{k}B_k. $ Thus the statement holds for \(n=1\).
Inductive Step: Assume that for some \(n\ge1\), $ B_n = \sum_{k=0}^{n-1} \binom{n-1}{k}B_k. $ We must show that $ B_{n+1} = \sum_{k=0}^{n} \binom{n}{k}B_k. $ Consider partitions of the set $ \{1,2,\dots,n,n+1\}. $ Fix the subset containing the element \(n+1\). Suppose this subset contains exactly \(n-k\) other elements chosen from the first \(n\) elements. The remaining \(k\) elements must then be partitioned arbitrarily into nonempty subsets. This can be done in $ B_k $ ways. Also, the \(k\) remaining elements can be chosen from the first \(n\) elements in $ \binom{n}{k} $ ways. Therefore, for each \(k\), the number of partitions is $ \binom{n}{k}B_k. $ Summing over all possible values of \(k\) gives $ B_{n+1} = \sum_{k=0}^{n} \binom{n}{k}B_k. $
By the principle of mathematical induction, the recurrence relation holds for all \(n\ge1\).
Comments
Post a Comment