I have problems proving this equality: $$1+\frac{n}{1!}+\frac{n*(n-1)}{2!}+\frac{n*(n-1)*(n-2)}{3!}+...+\frac{n*(n-1)...3*2}{(n-1)!}+\frac{n!}{n!}=2^n$$ Tried various options in inductive step of separating each addends that didn't help much.
EDIT: Any other way of solving this other then using Newton's binomial theorem ? I'm looking for a basic induction.
On
First, notice that for all k $n \choose{k}$ = $\frac{n!}{(n-k)!*k!}$ = $\frac{n*(n-1)*..*(n-k+1)}{k!}$ So the left side of the equation can be written as $\sum_{k=1}^{n}{n \choose{k}}$
Now try to use ${n-1\choose{k-1}}+{n-1\choose k}={n\choose k}$ to split the sum.
The equality is proven here:Binomial coefficient proof for ${n\choose m-1}+{n\choose m}={n+1\choose m}$ to split the sum.
On
This looks like you're trying to show that: $$ S_{n} =\sum_{j = 0}^{n} \dfrac{n!}{(n - j)!j!} = 2^{n} $$ each iteration of this sum is exactly the formula for choosing $j$ objects from a collection of $n$ objects where order doesn't matter (combinations) This is also the formula for the number subsets of a power set with $n$ elements and the way to find the sum of the $n$th row of Pascal's triangle.
Here is a Proof of the cardinality of a Power-set Using Induction (proof 3) that sketches the steps you need to take
Edit:
If you want to get there strictly by manipulating what you've been given I'd start by realizing that the first term (obviously) and last term of your sum are equal to 1, that the second and penultimate term are equal to $n$, that this is a convergent sum (and so rearrangeable) and that if we rewrite these pieces of my sum as $2, \textrm{ and } 2n$ ,respectively and that I can factor out $n(n-1)(n-2)$ from each of my remaining terms and that this number must be even (in other words I'm going to be able to fact out 2 from all of my terms)
Hints:
$$\begin{align*}&\text{ Your sum is simply}\;\;\sum_{k=0}^n\binom nk=\sum_{k=0}^n\binom nk 1^k\cdot 1^{n-k}\\{}\\ &\text{ Newton's Binomial Theorem:}\;\;(a+b)^n=\sum_{k=0}^n\binom nk a^kb^{n-k}\end{align*}$$