C n 0 + C n 1 + ⋯ + C n n = 2 n C_n^0+C_n^1+\cdots+C_n^n=2^nCn0+Cn1+⋯+Cnn=2n
( x + y ) n = C n 0 x n y 0 + C n 1 x n − 1 y 1 + ⋯ + C n n x 0 y n (x+y)^n=C_n^0x^ny^0+C_n^1x^{n-1}y^1+\cdots+C_n^nx^0y^n(x+y)n=Cn0xny0+Cn1xn−1y1+⋯+Cnnx0yn, set x = y = 1 x=y=1x=y=1.A combination is a selection of items from a collection, such that the order of selection does not matter: ( n k ) = n ( n − 1 ) ⋯ ( n − k + 1 ) k ( k − 1 ) ⋯ 1 = n ! k ! ( n − k ) ! . \binom{n}{k} =\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1} = \frac{n!}{k!(n-k)!}.(kn)=k(k−1)⋯1n(n−1)⋯(n−k+1)=k!(n−k)!n!.
Prove S n S_nSn: n ! > 2 n n!>2^nn!>2n is true for n ≥ 4 n\geq4n≥4 using Mathematical Induction.
Proof.
Base case: 4 ! = 24 > 2 4 = 16 4!=24>2^4=164!=24>24=16, so S 4 S_4S4 is true.
Induction Hypothesis (I. H.): suppose k ! > 2 k k!>2^kk!>2k is true for some arbitrary k ≥ 4 k\geq4k≥4.
Induction Step (need to show ( k + 1 ) ! > 2 k + 1 = 2 k ⋅ 2 = 2 k + 2 k (k+1)!>2^{k+1}=2^k\cdot2=2^k +2^k(k+1)!>2k+1=2k⋅2=2k+2k):
( k + 1 ) ! = ( k + 1 ) ⋅ k ! = k ⋅ k ! + k ! > k ⋅ 2 k + 2 k ≥ 4 ⋅ 2 k + 2 k > 2 k + 2 k = 2 ⋅ 2 k = 2 k + 1 (k+1)!=(k+1)\cdot k!=k\cdot k!+k!>k\cdot 2^k+2^k\geq 4\cdot 2^k+2^k>2^k+2^k=2\cdot 2^k=2^{k+1}(k+1)!=(k+1)⋅k!=k⋅k!+k!>k⋅2k+2k≥4⋅2k+2k>2k+2k=2⋅2k=2k+1. This shows S k + 1 S_{k+1}Sk+1 is true.
By Principle Mathematical Induction (PMI), S n S_nSn is true for all intergers n ≥ 4 n\geq 4n≥4.
有用的数学公式推导
版权声明：本文为u014261408原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。