Prove: Σ_(k=1) ^n ((n!)/((n−k)! k!))=2^n −1


Question and Answers Forum

All Questions Topic List
Arithmetic Questions
Previous in All Question Next in All Question
Previous in Arithmetic Next in Arithmetic
Question Number 4092 by Filup last updated on 28/Dec/15

$Prove :$ $\underset{k = 1}{\sum^{n}} \frac{n!}{(n - k)! k!} = 2^{n} - 1$
	Answered by Yozzii last updated on 28/Dec/15
	$According to the Binomial Theorem, for a,b being numbers of any kind (⇒a,b∈C) and n∈N+{0}, (a+b)^n =Σ_(k=0) ^n { ((n),(k) )a^(n−k) b^k } (∗) where ((n),(k) )=((n!)/((n−k)!k!)), (0≤k≤n). Observe that ((n),(0) )= ((n),(n) )=1. Suppose a=b=1.⇒a^(n−k) =1^(n−k) =1 and b^k =1^k =1. ∴ a^(n−k) b^k =1×1=1 Also, a+b=1+1=2. Subsituting this information into (∗) we obtain 2^n =Σ_(k=0) ^n { ((n),(k) )×1}= ((n),(0) )+Σ_(k=1) ^n { ((n),(k) )} ⇒Σ_(k=1) ^n { ((n),(k) )}=2^n −1. Equivalently, we can write Σ_(k=1) ^n {((n!)/((n−k)!k!))}=2^n −1. ■$
	$A c c o r d i n g t o t h e B i n o m i a l T h e o r e m,$ $f o r a, b b e i n g n u m b e r s o f a n y k i n d$ $(\Rightarrow a, b \in C) a n d n \in N + {0},$ ${(a + b)}^{n} = \underset{k = 0}{\sum^{n}} {(\begin{matrix} n \\ k \end{matrix}) a^{n - k} b^{k}} ()$ $w h e r e (\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{(n - k)! k!}, (0 ⩽ k ⩽ n) .$ $O b s e r v e t h a t (\begin{matrix} n \\ 0 \end{matrix}) = (\begin{matrix} n \\ n \end{matrix}) = 1 .$ $S u p p o s e a = b = 1 . \Rightarrow a^{n - k} = 1^{n - k} = 1$ $a n d b^{k} = 1^{k} = 1 . ∴ a^{n - k} b^{k} = 1 \times 1 = 1$ $A l s o, a + b = 1 + 1 = 2 . S u b s i t u t i n g t h i s$ $i n f o r m a t i o n i n t o () w e o b t a i n$ $2^{n} = \underset{k = 0}{\sum^{n}} {(\begin{matrix} n \\ k \end{matrix}) \times 1} = (\begin{matrix} n \\ 0 \end{matrix}) + \underset{k = 1}{\sum^{n}} {(\begin{matrix} n \\ k \end{matrix})}$ $\Rightarrow \underset{k = 1}{\sum^{n}} {(\begin{matrix} n \\ k \end{matrix})} = 2^{n} - 1 .$ $E q u i v a l e n t l y, w e c a n w r i t e$ $\underset{k = 1}{\sum^{n}} {\frac{n!}{(n - k)! k!}} = 2^{n} - 1 . ◼$
	Commented by Yozzii last updated on 28/Dec/15
	$Proof of Binomial Theorem: Let P(n) be the proposition that,∀n∈N+{0}, (a+b)^n =Σ_(k=0) ^n ((n),(k) )a^(n−k) b^k (∗) where a,b∈C and ((n),(k) )=((n!)/((n−k)!k!)) (0≤k≤n). Let n=0.⇒l.h.s of (∗)=(a+b)^0 =1. r.h.s=Σ_(k=0) ^0 ((0),(k) )a^(0−k) b^k = ((0),(0) )a^(0−0) b^0 = ((0),(0) ) ∵ ((0),(0) )=((0!)/((0−0)!0!))=(1/(0!×1))=(1/1)=1 ⇒r.h.s=1=l.h.s. Hence, P(n) is true when n=0. Assume P(n) is true when n=j (>0) ⇒(a+b)^j =Σ_(k=0) ^j ((j),(k) )a^(j−k) b^k . For n=j+1, (a+b)^(j+1) =(a+b)(a+b)^j =(a+b)(Σ_(k=0) ^j { ((j),(k) )a^(j−k) b^k }) (a+b)^(j+1) =Σ_(k=0) ^j { ((j),(k) )a^(j+1−k) b^k }+bΣ_(k=0) ^j ((j),(k) )a^(j−k) b^k } We acknowledge the following identity for (((j+1)),(k) ). (((j+1)),(k) )= ((j),(k) )+ ((j),((k−1)) ) Proof: The definition of ((n),(k) ) is used. ((j),(k) )+ ((j),((k−1)) )=((j!)/((j−k)!k!))+((j!)/((j−k+1)!(k−1)!)) =((j!)/((j−k)!(k−1)!)){(1/k)+(1/(j−k+1))} =((j!)/((j−k)!(k−1)!))(((j+1−k+k)/(k(j+1−k)))) =((j!(j+1))/((j−k+1)!k!)) =(((j+1)!)/(({j+1}−k)!k!)) = (((j+1)),(k) ) □ Note that ((n),(k) )=0 for k<0 ∴ (a+b)^(j+1) =Σ_(k=0) ^j {( (((j+1)),(k) )− ((j),((k−1)) ))a^(j+1−k) b^k +b(a+b)^n =Σ_(k=0) ^j (((j+1)),(k) )a^(j+1−k) b^k +b(a+b)^j −Σ_(k=0) ^j ((j),((k−1)) )a^(j+1−k) b^k =Σ_(k=0) ^(j+1) { (((j+1)),(k) )a^(j+1−k) b^k }−b^(j+1) +b^(j+1) +Σ_(k=0) ^(j−1) { ((j),(k) )a^(j−k) b^(k+1) }−( ((j),((−1)) )a^(j+1) +Σ_(k=1) ^j { ((j),((k−1)) )a^(j+1−k) b^k }) =Σ_(k=0) ^(j+1) { (((j+1)),(k) )a^(j+1−k) b^k }+0+ ((j),(0) )a^j b− ((j),(0) )a^j + ((j),(1) )a^(j−1) b^2 − ((j),(1) )a^(j−1) b^2 + ((j),(2) )a^(j−2) b^3 − ((j),(2) )a^(j−2) b^3 +...+ ((j),((j−2)) )a^2 b^(j−1) − ((j),((j−2)) )a^2 b^(j−1) + ((j),((j−1)) )ab^j − ((j),((j−1)) )ab^j ⇒(a+b)^(j+1) =Σ_(k=0) ^(j+1) (((j+1)),(k) )a^(j+1−k) b^k Hence,P(j+1) is true,assuming P(j) is true. Since P(0) is true then, by the principle of mathematical induction, P(n) is true ∀n∈N+{0}.$
	$P r o o f o f B i n o m i a l T h e o r e m :$ $L e t P (n) b e t h e p r o p o s i t i o n t h a t, \forall n \in N + {0},$ ${(a + b)}^{n} = \underset{k = 0}{\sum^{n}} (\begin{matrix} n \\ k \end{matrix}) a^{n - k} b^{k} ()$ $w h e r e a, b \in C a n d (\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{(n - k)! k!} (0 ⩽ k ⩽ n) .$ $L e t n = 0 . \Rightarrow l . h . s o f () = {(a + b)}^{0} = 1 .$ $r . h . s = \underset{k = 0}{\sum^{0}} (\begin{matrix} 0 \\ k \end{matrix}) a^{0 - k} b^{k} = (\begin{matrix} 0 \\ 0 \end{matrix}) a^{0 - 0} b^{0} = (\begin{matrix} 0 \\ 0 \end{matrix})$ $∵ (\begin{matrix} 0 \\ 0 \end{matrix}) = \frac{0!}{(0 - 0)! 0!} = \frac{1}{0! \times 1} = \frac{1}{1} = 1$ $\Rightarrow r . h . s = 1 = l . h . s .$ $H e n c e, P (n) i s t r u e w h e n n = 0 .$ $A s s u m e P (n) i s t r u e w h e n n = j (> 0)$ $\Rightarrow {(a + b)}^{j} = \underset{k = 0}{\sum^{j}} (\begin{matrix} j \\ k \end{matrix}) a^{j - k} b^{k} .$ $F o r n = j + 1,$ ${(a + b)}^{j + 1} = (a + b) {(a + b)}^{j} = (a + b) (\underset{k = 0}{\sum^{j}} {(\begin{matrix} j \\ k \end{matrix}) a^{j - k} b^{k}})$ ${(a + b)}^{j + 1} = \underset{k = 0}{\sum^{j}} {(\begin{matrix} j \\ k \end{matrix}) a^{j + 1 - k} b^{k}} + b \underset{k = 0}{\sum^{j}} (\begin{matrix} j \\ k \end{matrix}) a^{j - k} b^{k}}$ $W e a c k n o w l e d g e t h e f o l l o w i n g i d e n t i t y$ $f o r (\begin{matrix} j + 1 \\ k \end{matrix}) .$ $(\begin{matrix} j + 1 \\ k \end{matrix}) = (\begin{matrix} j \\ k \end{matrix}) + (\begin{matrix} j \\ k - 1 \end{matrix})$ $P r o o f :$ $T h e d e f i n i t i o n o f (\begin{matrix} n \\ k \end{matrix}) i s u s e d .$ $(\begin{matrix} j \\ k \end{matrix}) + (\begin{matrix} j \\ k - 1 \end{matrix}) = \frac{j!}{(j - k)! k!} + \frac{j!}{(j - k + 1)! (k - 1)!}$ $= \frac{j!}{(j - k)! (k - 1)!} {\frac{1}{k} + \frac{1}{j - k + 1}}$ $= \frac{j!}{(j - k)! (k - 1)!} (\frac{j + 1 - k + k}{k (j + 1 - k)})$ $= \frac{j! (j + 1)}{(j - k + 1)! k!}$ $= \frac{(j + 1)!}{({j + 1} - k)! k!}$ $= (\begin{matrix} j + 1 \\ k \end{matrix}) ◻$ $N o t e t h a t (\begin{matrix} n \\ k \end{matrix}) = 0 f o r k < 0$ $∴ {(a + b)}^{j + 1} = \underset{k = 0}{\sum^{j}} {((\begin{matrix} j + 1 \\ k \end{matrix}) - (\begin{matrix} j \\ k - 1 \end{matrix})) a^{j + 1 - k} b^{k} + b {(a + b)}^{n}$ $= \underset{k = 0}{\sum^{j}} (\begin{matrix} j + 1 \\ k \end{matrix}) a^{j + 1 - k} b^{k} + b {(a + b)}^{j} - \underset{k = 0}{\sum^{j}} (\begin{matrix} j \\ k - 1 \end{matrix}) a^{j + 1 - k} b^{k}$ $= \underset{k = 0}{\sum^{j + 1}} {(\begin{matrix} j + 1 \\ k \end{matrix}) a^{j + 1 - k} b^{k}} - b^{j + 1} + b^{j + 1} + \underset{k = 0}{\sum^{j - 1}} {(\begin{matrix} j \\ k \end{matrix}) a^{j - k} b^{k + 1}} - ((\begin{matrix} j \\ - 1 \end{matrix}) a^{j + 1} + \underset{k = 1}{\sum^{j}} {(\begin{matrix} j \\ k - 1 \end{matrix}) a^{j + 1 - k} b^{k}})$ $= \underset{k = 0}{\sum^{j + 1}} {(\begin{matrix} j + 1 \\ k \end{matrix}) a^{j + 1 - k} b^{k}} + 0 + (\begin{matrix} j \\ 0 \end{matrix}) a^{j} b - (\begin{matrix} j \\ 0 \end{matrix}) a^{j}$ $+ (\begin{matrix} j \\ 1 \end{matrix}) a^{j - 1} b^{2} - (\begin{matrix} j \\ 1 \end{matrix}) a^{j - 1} b^{2} + (\begin{matrix} j \\ 2 \end{matrix}) a^{j - 2} b^{3}$ $- (\begin{matrix} j \\ 2 \end{matrix}) a^{j - 2} b^{3} + . . . + (\begin{matrix} j \\ j - 2 \end{matrix}) a^{2} b^{j - 1} - (\begin{matrix} j \\ j - 2 \end{matrix}) a^{2} b^{j - 1}$ $+ (\begin{matrix} j \\ j - 1 \end{matrix}) {a b}^{j} - (\begin{matrix} j \\ j - 1 \end{matrix}) {a b}^{j}$ $\Rightarrow {(a + b)}^{j + 1} = \underset{k = 0}{\sum^{j + 1}} (\begin{matrix} j + 1 \\ k \end{matrix}) a^{j + 1 - k} b^{k}$ $H e n c e, P (j + 1) i s t r u e, a s s u m i n g P (j)$ $i s t r u e . S i n c e P (0) i s t r u e t h e n, b y t h e$ $p r i n c i p l e o f m a t h e m a t i c a l i n d u c t i o n,$ $P (n) i s t r u e \forall n \in N + {0} .$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum