Intereting Posts

From distribution to Measure
Using Integration By Parts results in 0 = 1
How to show that $L^p$ spaces are nested?
Natural density of solvable quintics
some questions about combinations
Adding equations in Triangle Inequality Proof
Mnemonics for linear algebra
Is this $\gcd(0, 0) = 0$ a wrong belief in mathematics or it is true by convention?
Inside a card deck there are 52 cards with 4 colors, 13 cards for each color
Proving $\lim\limits_{x\to0}\left(\frac{1}{\log(x+\sqrt{1+x^2})}-\frac{1}{\log(1+x)}\right) =-\frac12$
Periodic orbits
Proving that the dot product is distributive?
Counting edges in a specially defined graph
Chain rule for multivariable functions confusion
Can $\mathbb R$ be written as the disjoint union of (uncountably many) closed intervals?

Student here! Just reading Liebecks Introduction to pure mathematics for fun and I made an attempt at proving the total number of subsets of S is equal to $2^n$.

I realized that the total number of subsets of S is just:

$ \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} + 1$

- Number of monomials of certain degree
- Category of binomial rings
- Prove $\sum \binom nk 2^k = 3^n$ using the binomial theorem
- Binomial coefficients based question
- Show this equality (The factorial as an alternate sum with binomial coefficients).
- Inequality $\binom{2n}{n}\leq 4^n$

And so I put together the cool looking formula

$ \displaystyle \sum_{r=1}^n \frac{n!}{r!(n-r)!} = 2^n – 1$

But I have no clue how to approach proving this formula analytically. Any help?

So if I try a proof by induction:

$\displaystyle \sum_{r=1}^n \frac{n!}{r!(n-r)!} = 2^n – 1$

$\displaystyle \sum_{r=0}^n \frac{n!}{r!(n-r)!} = 2^n$

obviously true for $n = 1$:

$1 + \frac{1}{1!0!} = 2 = 2$

assume true for $n$, I could multiply both sides by $2$?

$\displaystyle 2\sum_{r=0}^n \frac{n!}{r!(n-r)!} = 2^{n+1}$

How could I go about proving that

$\displaystyle 2\sum_{r=0}^n \frac{n!}{r!(n-r)!} = \sum_{r=0}^{n+1} \frac{(n+1)!}{r!((n+1) – r)!}$

- If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$ are divisible by $pq$?
- Painting the faces of a cube with distinct colours
- Probability of having $k$ similar elements in two subsets.
- Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$
- The number of ways to order 26 alphabet letters, no two vowels occurring consecutively
- Term independent of x and y in this expansion
- Evaluating 'combinatorial' sum
- Where are good resources to study combinatorics?
- How many words can be formed from 'alpha'?
- About counting number of n-tuples

You can prove it by induction.

First off start by noticing that $$ \displaystyle \sum_{r=1}^n \frac{n!}{r!(n-r)!} = 2^n – 1\iff \displaystyle \sum_{r=0}^n \overbrace{\frac{n!}{r!(n-r)!}}^{\displaystyle \binom{n}{r}} = 2^n$$

Due to the equivalence above, it suffices to prove that $\displaystyle \sum_{r=0}^n \binom{n}{r} = 2^n$. (The only reason I chose to prove this one instead is because I feel it is more aesthetically pleasing).

**Base case:** $n=0$

$\displaystyle \sum_{r=0}^0 \binom{0}{r} = \displaystyle \sum_{r=0}^0 \frac{0!}{r!(0-r)!} = \frac{0!}{0!0!}=1=2^0$

**Induction step:** Let $n\in \Bbb N$ and suppose $\displaystyle \sum_{r=0}^n \binom{n}{r} = 2^n$. Multiply by $2$ to get: $$\displaystyle 2\sum_{r=0}^n \binom{n}{r} = 2^{n+1}.$$

Also that is left is to prove that $\displaystyle 2\sum_{r=0}^n \binom{n}{r}=\sum_{r=0}^{n +1}\binom{n+1}{r}$. The green equality below is a consequence of Pascal’s rule:

$$\begin{align}

2\sum_{r=0}^n \binom{n}{r}&=\sum_{r=0}^n \binom{n}{r}+\sum_{r=0}^n \binom{n}{r}\\

&=\binom{n}{0}+\sum_{\color{red}{r=1}}^n \binom{n}{r}+\sum_{r=0}^{\color{blue}{n-1}} \binom{n}{r}+\binom{n}{n}\\

&=1+\sum_{\color{red}{r=0}}^\color{red}{n-1} \binom{n}{\color{red}{r+1}}+\sum_{r=0}^{{n-1}} \binom{n}{r}+1\\

&=1+\sum _{r=0}^{n-1}\left[\binom{n}{r+1}+\binom{n}{r}\right]+1\\

&\color{green}=1+\sum_{r=0}^{n-1} \binom{n+1}{r+1} + 1\\

&=\binom{n+1}{0}+\sum _{\color{red}{r=1}}^\color{red}n\binom{n+1}{\color{red}r}+\binom{n+1}{n+1}\\

&=\binom{n+1}{0}+\sum _{r=1}^{n+1}\binom{n+1}{r}\\

&=\sum _{r=0}^{n+1}\binom{n+1}{r}

\end{align}$$

Note that starting on the third line I use $n-1$. This is only correct if $n\ge 1$, but if $n=0$, it’s just the base case.

I just noticed that your base case is for $n=1$, that’s fine. Mine is a bit more general.

Hint: To form a subset, for each element of $S$ we have to decide whether to include or to exclude that element. If $|S| = n$, $n$ decisions must be made.

This can be proved by simple approach as :

Suppose S is $ S = \lbrace a_1,a_2,a_3,………….a_n \rbrace $

For subset a element can be selected in 2 way,either it is selected or not selected.

So total subset is :

$ \lbrace 2.2.2.2…………2\rbrace $ \\ n times multiplication of 2

$ = 2^n $

Let the statement be denoted by P(N) Case N=0… Clearly a set with no elements is Null set…(Phi) there fore has only Null set as its subset. As 2^0 is 1… P(0) is correct.

Case N=1… Clearly a set with 1 element has only 2 subsets,that and null set. As 2^1 is 2… P(1) is correct.

Now suppose P(x) is true where x is a Natural number. ie a set having x no. of elements has 2^x subsets.

we have to prove that P(x+1) is true. ie, a set having x+1 elements has 2^(x+1) subsets. In this set we have n1,n2….nx and then nx+1 newly added apart from the subsets that can be formed with n1,n2…nx… we can form additional subsets by choosing any number from 1 to x among n1,n2…nx… ie,xC0+xC1+…. xC = 2^x (xC0 for a set with nx+1 alone). Now trying to account for a total it becomes 2^x+2^x = 2*2^x = 2^(x+1)

Thus by principle of induction P(x) is true for all x=0,1,2…

Do you know this is just the binomial formula? It states

\begin{equation}

(a+b)^n = \sum_{k=0}^n {n \choose k} a^k b^{n-k}

\end{equation}

Take $a=b=1$ to get your formula.

- Looking for closed-forms of $\int_0^{\pi/4}\ln^2(\sin x)\,dx$ and $\int_0^{\pi/4}\ln^2(\cos x)\,dx$
- Show a stochastic process is a martingale using Ito's lemma
- Proof of Bolzano's Theorem
- Variable leaving basis in linear programming – when does it happen?
- Is there a continuous function such that $\int_0^{\infty} f(x)dx$ converges, yet $\lim_{x\rightarrow \infty}f(x) \ne 0$?
- Is there a similar concept for a sigma algebra like a base for a topology?
- Show that every graph $G$ has a bipartite subgraph with at least half of the edges of $G$
- Finding variance of the sample mean of a random sample of size n without replacement from finite population of size N.
- The Relative Values of Two Modified Bessel Function of the First Kind
- If every $x\in X$ is uniquely $x=y+z$ then $\|z\|+\|y\|\leq C\|x\|$
- Disprove the Twin Prime Conjecture for Exotic Primes
- Linear algebra proof regarding matrices
- Prime Divisors of $x^2 + 1$
- The definition of locally Lipschitz
- find all self-complementary graphs on five vertices