1

My teacher substitutes for this $\sum_{x=0}^{y} ({{y!} \over {x! (y-x)!} })$ by $2^y$, so I tried to use the (Mathematical induction) to prove it (My teacher did not ask me to do that, however I want to do it only to make sure for this statement)

My attempt:

  • when $y=1$ :

L.H.S. $2^y=2$

R.H.S. $\sum_{x=0}^{1} {{y!} \over {x! (y-x)!} } =2$

So this true when $y=1$

  • Let the statement true when $y=k$ , so

$\sum_{x=0}^{k} {{k!} \over {x! (k-x)!} } =2^k$

  • When $y=k+1$

L.H.S.

$2^y=2^{k+1}=2*2^k=2 * \sum_{x=0}^{k} {{k!} \over {x! (k-x)!} }$

R.H.S

$\sum_{x=0}^{k+1} {{(k+1)!} \over {x! (k-x+1)!} }=\sum_{x=0}^{k+1} {({k+1)k!} \over {x! (k-x+1)(k-x)!} }$

But now I don't know how can I complete it ?

Imago
  • 2,132
Dima
  • 2,479
  • Thanks, I fixed that. @ThomasAndrews – Dima Mar 06 '17 at 14:35
  • 1
    Use 2^{k+1} rather than 2^(k+1). The latter formats as $2^(k+1)$, which is not what you want. – Thomas Andrews Mar 06 '17 at 14:35
  • 1
    Plenty of approaches exist, for example, if you are into induction proofs, a direct proof follows from the identity $${k+1\choose y}={k\choose y}+{k\choose y-1}$$ – Did Mar 06 '17 at 14:36

2 Answers2

3

Observe that $$\sum_{x=0}^y\frac{y!}{x!(y-x)!}=\sum_{x=0}^y{y\choose x}$$ This correspond to the develop of $2^y=(1+1)^y\;$ from the Binomial Theorem.

Ángel Mario Gallegos
  • 19,882
1

You can verify it easily. The terms in LHS are $\frac{y!}{x!(y-x)!}$ which means the way you can choose $x$ objects form $y$ objects. The sum over $x$ will give you total ways to select a object from $y$ objects which is $2^y$ since it is about select or not select i.e. 2 ways, i.e. in all total $2^y$ ways.

$(1+p)^y= \sum_{x=0}^{y} \frac{y!}{x!(y-x)!} p^x$, take $p=1$

MAN-MADE
  • 5,381