discrete mathematics - 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.

Answer

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.