2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Commented Mar 23, 2016 at 3:56
  • $\begingroup$ 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 $\endgroup$ Commented Mar 23, 2016 at 3:59
  • 1
    $\begingroup$ Ah, I see. Thanks, @user52969 $\endgroup$
    – CSstudent
    Commented Mar 23, 2016 at 4:00
  • $\begingroup$ Well the number 2 doesn't need induction at all. $$n^3+3n^2+2n=n(n+1)(n+2)$$ $\endgroup$ Commented Mar 23, 2016 at 5:05

3 Answers 3

4
$\begingroup$

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.

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

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – CSstudent
    Commented Mar 23, 2016 at 4:31
  • $\begingroup$ Anytime...happy to help. $\endgroup$
    – GRrocks
    Commented Mar 23, 2016 at 4:36
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .