Discrete Mathematics: Induction

Induction

Prove each of the following statements using mathematical induction.

1. Triangular Numbers (Sum of First \(n\) Positive Integers):
   
   \[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \]



Example. $N=4$




2. Sum of Odd Numbers:
   
   \[ 1 + 3 + 5 + \cdots + (2n-1) = n^2 \]


3. Sum of First \(n\) Square Numbers:
   
   \[ 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} \]


4. 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} \]


5. Sum of First \(n\) Cubes:
   
   \[ 1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]


6. Geometric Series Partial Sum:
   
   \[ \sum_{k=0}^{n-1} ar^k = \frac{a(1-r^n)}{1-r}, \quad r \ne 1 \]


7. Cardinality of the Power Set:
   
   \[ |P(A)| = 2^{|A|} \]


8. Pascal's Identity:
   
   \[ \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}, \quad n \ge 0,\; 1 \le k \le n \]


9. Hockey-Stick Identity:
   
   \[ \sum_{k=r}^n \binom{k}{r} = \binom{n+1}{r+1}, \quad n \ge r \ge 0 \]


10. Sum of Binomial Coefficients:
    
    \[ \sum_{k=0}^n \binom{n}{k} = 2^n, \quad n \ge 0 \]


11. Symmetry of Binomial Coefficients:
    
    \[ \binom{n}{k} = \binom{n}{n-k}, \quad n \ge 0,\; 0 \le k \le n \]


12. Central Binomial Coefficient Maximum:
    
    \[ \binom{n}{k} \le \binom{n}{\lfloor n/2 \rfloor}, \quad n \ge 1,\; 0 \le k \le n \]


13. Derangement Recurrence:
    
    \[ D_0=1,\quad D_1=0,\quad D_n=(n-1)\bigl(D_{n-1}+D_{n-2}\bigr), \quad n \ge 2 \]
    
    where \(D_n\) denotes the number of derangements of \(n\) distinct elements.


14. Stirling Numbers of the Second Kind Recurrence:
    
    \[ S(n,k)=kS(n-1,k)+S(n-1,k-1), \quad n \ge 1,\; 1 \le k \le n \]


15. Bell Number Recurrence:
    
    \[ B_n=\sum_{k=0}^{n-1}\binom{n-1}{k}B_k, \quad n \ge 1 \]