# Thread: More Inductive Proof Questions

1. ## More Inductive Proof Questions

Hi guys, here I am again! I've been doing fine, even mowing through with what I feel are normal Inductive Proof Questions like:

1 x 3 x 5 + 2 x 4 x 6 + ... + n(n+2)(n+4) = (n/4)(n+1)(n+4)(n+5)

but now I've hit a point in the book where it doesn't feel so straightforward, and honestly I still don't get it.

Point 1. Just to clarify for myself, in proof by induction, the goal is to take the next step on the left hand side of the statement, and stick it onto the right hand side as well, then, using mathematical techniques learnt factorize the right hand side so every n becomes n+1 to indicate that the statement is still true for whatever value n is.

Point 2. The textbook has started asking questions that kind of boggle me, but I believe it's because I might be missing some small technique or approach to solving them. An example of these questions involve:

Question 1:
Use Proof by induction to prove that:
(x-1) is a factor of xn - 1-1
for all positive integer values of n

Question 2:
Use Proof by induction to prove that:
1 x 2 x 3 x 4 x 5 x 6 x ... x n ≥ 3n
where n > 6

Question 3:
Use Proof by induction to prove that:
7n + 2 * 13n
is a multiple of 3 for all n ≥ 0

These types of questions definitely don't follow the styles of the questions they come after. Its really the Inductive Step that I get trouble with.
Could it possibly because my point 1(somewhere above) is wrong?

Note: Please don't give me the answers because I don't have many of these questions. Maybe just a pointer or direction?
Thanks!

2. ## Re: More Inductive Proof Questions

Originally Posted by ACARROT
Hi guys, here I am again! I've been doing fine, even mowing through with what I feel are normal Inductive Proof Questions like:

1 x 3 x 5 + 2 x 4 x 6 + ... + n(n+2)(n+4) = (n/4)(n+1)(n+4)(n+5)

but now I've hit a point in the book where it doesn't feel so straightforward, and honestly I still don't get it.

Point 1. Just to clarify for myself, in proof by induction, the goal is to take the next step on the left hand side of the statement, and stick it onto the right hand side as well, then, using mathematical techniques learnt factorize the right hand side so every n becomes n+1 to indicate that the statement is still true for whatever value n is.

Point 2. The textbook has started asking questions that kind of boggle me, but I believe it's because I might be missing some small technique or approach to solving them. An example of these questions involve:

Question 1:
Use Proof by induction to prove that:
(x-1) is a factor of xn - 1-1
for all positive integer values of n
I'm not sure I understand what your "point 1" says. To prove statement P(n) "by induction", you need to do two things:
1) Prove that P(1) is true (or P(0) or whatever your starting value is).
2) Prove that if P(k) is true then P(k+1).

Here "P(n)" is "x- 1 is a factor of $\displaystyle x^{n-1}- 1$ for n a positive integer". The smallest "positive integer" is 1 and P(1) is "$\displaystyle x^{1- 1}- 1= x^0- 1= 1- 1= 0$ is divisible by x- 1 which is certainly true- 0 is divisible by anything.

Now, suppose P(k) is true- that $\displaystyle x^{k-1}- 1$ is divisible by x- 1. To prove P(k+1) we have to prove that $\displaystyle x^{k-1+ 1}- 1= x^k- 1$ is divisible by x- 1. Clearly, we want to go from $\displaystyle x^k- 1$ to [tex]x^{k-1}- 1[tex]. Try writing $\displaystyle x^k- 1$ as [tex]x(x^{k-1})- 1= $\displaystyle x(x^{k-1})- x+ x- 1= x(x^{k-1}- 1)+ x- 1$.

Question 2:
Use Proof by induction to prove that:
1 x 2 x 3 x 4 x 5 x 6 x ... x n ≥ 3n
where n > 6
Or, phrased in another way, $\displaystyle n!\ge 3^n$. Here, the first value of n is n= 7 (because of "where n> 6").
When n= 7, this says 1 x 2 x 3 x 4 x 5 x 6 x 7= 5040 and $\displaystyle 3^7= 2187$. Yes, 5040> 2187.

Suppose that, for some k, $\displaystyle 1 x 2 x 3 x 4 x .... x k\ge 3^k$. Now look at $\displaystyle 1 x 2 x 3 x 4 x ... x k x (k+1)= (1 x 2 x 3 x 4 ... x k)x (k+1)\ge (3^k) x (k+1)$

[quote]Question 3:
Use Proof by induction to prove that:
7n + 2 * 13n
is a multiple of 3 for all n ≥ 0
The first value of n is 1. When n= 1, this is [tex]7^1+ 2*13^1= 7+ 26= 33= 3(11) so P(1) is true.

Now, suppose that, for some k, $\displaystyle 7^k+ 2(13^k)= 3a$ for some integer a (so is a multiple of 3). We look at n= k+1. $\displaystyle 7^{k+1}+ 2(13^{k+ 1})= 7(7^k)+ 2(13)(3^{k}= 7(7^k)+ 13(2)(13^k)= 7(7^k)+ 7(2)(13^k)+ 6(2)(13^k)= 7(7^k+ 2(13^k))+ 6(2)(13^k)= 7(3a)+ 6(2)(13^k)$.

These types of questions definitely don't follow the styles of the questions they come after. Its really the Inductive Step that I get trouble with.
Could it possibly because my point 1(somewhere above) is wrong?

Note: Please don't give me the answers because I don't have many of these questions. Maybe just a pointer or direction?
Thanks!

3. ## Re: More Inductive Proof Questions

You are thinking about these proofs way to mechanically.

You show P(1) is true. Then you say, assuming P(k) is true, then P(k+1) is true. How you do this second step is not reducible to rule. In general what you will have to do is to decompose P(k + 1) into P(k) and Q(k).

Step 1

$n = 1 \implies 7^n + 2 * 13^n = 7^1 + 2 * 13^1 = 7 + 26 = 33 = 3 * 11.$

Step 2

$\text {ASSUME: } k \in \mathbb N^+ \text { and } 3\ |\ 7^k + 2 * 13^k.$

$\therefore \exists\ a \in \mathbb N^+ \text { such that } 3a = 7^k + 2 * 13^k.$ Where did that come from?

It comes from the fact that $7^k + 2 * 13^k$ is evenly divisible by 3.

Now let's see what we are talking about with respect to k + 1 and see how we can express that in terms of k.

$7^{(k + 1)} + 2 * 13^{(k + 1)} =$

$7 * 7^k + 2 * 13 * 13^k.$

OK Now what? Well that $7^k$ looks familiar,

but it is multiplied by 7 and is missing $2 * 13^k$ to get where we want.

In this case we add 7 * 0.

$7 * 7^k + 2 * 13 * 13^k = 7 * 7^k + 7 * 0 + 2 * 13 * 13^k$

$7 * 7^k + 7(2 * 13^k - 2 * 13^k) + 2 * 13 * 13^k =$

$7(7^k + 2 * 13^k) - 14 * 13^k + 26 * 13^k = 7(7^k + 2 * 13^k) + 12 * 13^k.$

We now have something that is based on what we know about k and does not even mention k + 1. So

$7(7^k + 2 * 13^k) + 12 * 13^k = 7(3a) + 3 * 4 * 13^k = 3(7a + 4 * 13^k).$

$\text {But } 7,\ a,\ 4,\ k,\ 13^k \in \mathbb N^+ \implies b = 7a + 4 * 13^k \in \mathbb N^+.$

$\therefore 7^{(k + 1)} + 2 * 13^{(k + 1)} = 3b \implies 3\ |\ 7^{(k + 1)} + 2 * 13^{(k + 1)}.$

The trick is very general. You have to get your proposition about k + 1 related to what you have assumed about k. There is no mechanical way to do it. It requires creativity.