# Using the Principle of Mathematical Induction to Prove propositions

I have three questions regarding using the Principle of Mathematical Induction:

1. Let $P(n)$ be the following proposition:

$f(n) = f(n-1) + 1$ for all $n ≥ 1$, where $f(n)$ is the number of subsets of a set with $n$ elements.

2. Let $P(n)$ be the following proposition:

$n^3 + 3n^2 + 2n$ is divisible by 3 for all $n ≥ 1$. Determine whether $P(n)$ holds.

3. Use the Principle of Mathematical Induction to prove that $1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + ... + n \cdot n! = (n+1)! -1$ for all $n ≥ 1$.

Here is the work I have so far:

For #1, I am able to prove the basis step, 1, is true, as well as integers up to 5, so I am pretty sure this is correct. However, I am not able to come up with a formal proof.

For #2, for the basis step, I have $1^3 + 3(1)^2 + 2(1) = 6$, which is divisible by 3. For the inductive step, I need to prove that $P(k) \rightarrow P(k+1)$, so I have $P(k+1) = (k+1)^3 + 3(k+1)^2 + 2(k+1)$. However, I'm not sure how to take the inductive step and plug in the inductive hypothesis to make this formal proof true.

For #3, I think that the inductive hypothesis would be $\sum_{i=1} ^ {k+1} i \cdot i! = (k+2)! -1$. When I do this, I am getting $\sum_{i=1} ^ {k+1} i \cdot i! = \sum_{i=1} ^ k (k+1)! + \sum_{i=1} ^ 1 1! - 1$ , but I don't think this will work for plugging in the inductive hypothesis. I think I should be using $1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + ... + n \cdot n! + n+1 \cdot n+1! = (n+2)! -1$ instead for the proof. I'm getting nowhere with this one.

Any help would be appreciated.

• the number of subsets for a set with order $n$ is $2^n$. Consequently, $2^n-1 \neq 2^{n-1}$ in general, so it is false – Andres Mejia Mar 23 '16 at 3:56
• for #1, check again. for n = 2, you have {}, {1}, {2}, and {1, 2} as possible subsets of {1 , 2}, so 4 subsets, but only {} and {1} are the possible subsets of {1}, which is only 2 subsets. you're claiming 4 = 2 + 1, which is false – user52969 Mar 23 '16 at 3:59
• Ah, I see. Thanks, @user52969 – CSstudent Mar 23 '16 at 4:00
• Well the number 2 doesn't need induction at all. $$n^3+3n^2+2n=n(n+1)(n+2)$$ – TheRandomGuy Mar 23 '16 at 5:05

## 3 Answers

the number of subsets for a set with order $n$ is $2^n$. Consequently, $2^n-1 \neq 2^{n-1}$ in general, so it is false.

To prove this fact, you can actually use induction!

More specifically, think about the number of ways you can have a k-element subset which is going to be$\dbinom{n}{k}$ [how many ways can you pick a group of k people out of an $n$-person group.] Then all possible subsets will look like the total number of ways to be pick $k$-element subsets. In particular: $$\dbinom{n}{0}+\dbinom{n}{1}+...+\dbinom{n}{n}=2^n$$

For practice, try to prove this with induction.

For (2), the base case is clear. We assume that $3 \mid n^3+3n^2+2n$. This means that there exists some integer $k$ so that $3k=n^3+3n^2+2n$

Then: \begin{align}(n+1)^3+3(n+1)^2+2(n+1)&=(n^3+3n^2+3n+1)+3(n^2+2n+1)+2n+2 \\ &=(n^3+3n^2+2n)+3n+3+3(n^2+2n+1)\\ \end{align} by substitution from the hypothesis, we obtain: \begin{align}&=3k+3(n^2+3n+2) \\ &=3(n^2+3n+2+k)\end{align}

Hence, the result follows readily.

I leave part 3 to you. You got the induction step correctly, at least in the set up. Try some algebraic manipulation to start with; keep in mind what your assumption is, you just want it to show up somewhere in your inductive step. Induction is an easy enough idea, but the problem is that it doesn't show much in the way of intuition. As in, it generally doesn't tell you why something works. We just get used to the fact that it solves problems for us. Kind of like l'hopital's rule in Calculus.

• Brilliant answer for the first part! – GRrocks Mar 23 '16 at 4:16
• haha @GRrocks, I believe that is a fairly standard explanation, but thank you nonetheless. – Andres Mejia Mar 23 '16 at 4:19
• Thanks, @AndresMejia ! I agree with you that it's not very intuitive. This helps a lot. – CSstudent Mar 23 '16 at 4:30

I'll help you out with the third one.

Say $P(k)$ is true, i.e.

$1.1!+2.2!+.....+k.k!=(k+1)!-1$. Add $(k+1).(k+1)!$ to both sides to get:

$1.1!+2.2!+.....+k.k!+(k+1)(k+1)!=(k+1)!-1+(k+1)(k+1)!$

$1.1!+2.2!+.....+k.k!+(k+1)(k+1)! =(k+1)![k+1+1]-1$=$(k+1)!(k+2)-1$; i.e.

$1.1!+2.2!+.....+k.k!+(k+1)(k+1)!=(k+2)!-1=((k+1)+1)-1$;

i.e. $P(k+1)$ is true.

So, by the first principle of induction, PROVED.

• Thank you! I think I was on the right track with my reasoning, but I was having a hard time getting from the second line to the third. – CSstudent Mar 23 '16 at 4:31
• Anytime...happy to help. – GRrocks Mar 23 '16 at 4:36

On #3, your mistake...$\sum_\limits{i=1}^{n+1} i(i!) = \sum_\limits{i=1}^{n} i(i!) + (n+1)(n+1)! = (n+1)! - 1 + (n+1)(n+1)!$

And you can take it from there.

If you wanted intuitive... looking at #2, you would say $n^3 + 3n^2 + 2n = n(n+1)(n+3)$ and one of those must be divisible by 3.

What is the principle of induction? If $0\in S$ and $n \in S \implies n+1\in S$ then all natural numbers are in $S$. $0$ is in $S$, and $1$ is in $S$ when $0$ is in $S$, and $2$ is in $S$ when $1$ is in $S$... And, that shouldn't be too un-intuitive a concept. It can be quite handy to crack problems that are not obvious by more direct application of algebra.