# Thread: More Inductive Proof Questions

1. ## More Inductive Proof Questions

I want to have a little 'le cry'.
Earlier today, I made a super detailed and tidy post on my question, but for some reason it didn't post(I think it was because of my internet), and now I've got to type it all again, and with less care and attention to detail.

Anyways, not so long ago, I had a query on this site regarding Inductive proofs, but now I've reached a point in the questions that I don't really see where I am meant to go in the inductive step.

Just to clarify, from what I have learnt, Inductive Proofs are:

Proving a statement is true for the defined values of a variable(e.g all positive integers) by
taking the next step of one side of the statement and adding it to the other, and then using
simplifying and factorising techniques to change every variable on the other side to the variable + 1.

Questions that seem relatively straightforward to me that I have been mowing through include:

Prove by induction that:

1 + 3 + 5 + 7 + ... + (2n-1) = n2
where n ≥ 1.
These are easy, as the next step on the left hand side is (2(n+1)-1) which is added to both sides and factorise to produce the right hand side as (n+1)2

But now I have reached questions that have full on stopped me in my tracks like:

Question 1Which has 2 variables?!)

Use proof by induction to prove that:
(x-1) is a factor of xn-1
when n ≥ 0.

Question 2Inequalities?)

Use proof by induction to prove that:
1 x 2 x 3 x 4 x 5 x 6 x ... x n ≥ 3n
When n > 6.

Question 3I would know how to do this kind of question in a proof by exhaustion or something)

Use proof by induction to prove that:
7n + 2 x 13n
is a multiple of 3 when n ≥ 0.

Which all have me soooo confused. Is it my understanding of how proof by induction works that is making me go off?
It would be more possible for me to think around it if it wasn't a proof by induction, but these have me having no clear idea of where to go.
I do have some working out, but they are definitely not worth any attention for now at least.

Please don't give me the answers, since I have a limited number of these questions, but maybe a pointer in the right direction or something would be great!
Thanks!

2. ## Re: More Inductive Proof Questions

Originally Posted by ACARROT
I want to have a little 'le cry'.
Earlier today, I made a super detailed and tidy post on my question, but for some reason it didn't post(I think it was because of my internet), and now I've got to type it all again, and with less care and attention to detail.

Anyways, not so long ago, I had a query on this site regarding Inductive proofs, but now I've reached a point in the questions that I don't really see where I am meant to go in the inductive step.

Just to clarify, from what I have learnt, Inductive Proofs are:

Proving a statement is true for the defined values of a variable(e.g all positive integers) by
taking the next step of one side of the statement and adding it to the other, and then using
simplifying and factorising techniques to change every variable on the other side to the variable + 1.
Well, there is your problem! No, that is not "proof by induction". Proof by induction, of statement P(n) which depends upon integer n, involves:
1) Prove the statement for 0, or 1, or what ever the smallest n for which P(n) is claimed to be true, really is true.
2) Assume the statement is true for some integer k and show it must be true for the next integer, k+ 1.

What you are talking about would be only step (2) for problems that involve addition, a very small set of problems.
Questions that seem relatively straightforward to me that I have been mowing through include:

Prove by induction that:

1 + 3 + 5 + 7 + ... + (2n-1) = n2
where n ≥ 1.
These are easy, as the next step on the left hand side is (2(n+1)-1) which is added to both sides and factorise to produce the right hand side as (n+1)2
Yes, those that involve addition- the very small set of function to which you incorrect idea of "proof by induction" applies.

But now I have reached questions that have full on stopped me in my tracks like:

Question 1Which has 2 variables?!)

Use proof by induction to prove that:
(x-1) is a factor of xn-1
when n ≥ 0.

There aren't really "two variables" since you are only concerned with n. You can treat "x" as a constant.
When n= 1, xn- 1= x- 1 so x- 1 is a factor.
Assume that, for some k, x- 1 is a factor of xk- 1: xk- 1= (x- 1)q(x) for some polynomial q. xk+1- 1= x(xk)- 1= x(xk- x+ x- 1= x(xk- 1)+ (x- 1)= x((x- 1)q(x))- (x- 1)= (x- 1)(xq(x)- 1).

[quote]Question 2Inequalities?)

Use proof by induction to prove that:
1 x 2 x 3 x 4 x 5 x 6 x ... x n ≥ 3n
When n > 6.
[QUOTE]
When n= 7 (the smallest integer greater than 6) 1 x 2 x 3 x 4 x 5 x 6 x 7= 5040 and 37= 2187. 5040> 2187

Assume that, for some k> 6, 1 x 2 x 3 x ... x k> 3k

Then 1 x 2 x 3 x ... x k x (k+1)= (1 x 2 x 3 x ... x k) x (k+1)> 3k x (k+ 1). But k> 6 so k+ 1> 6> 3. 3k x (k+1)> 3k x 3= 3k+ 1

Question 3I would know how to do this kind of question in a proof by exhaustion or something)

Use proof by induction to prove that:
7n + 2 x 13n
is a multiple of 3 when n ≥ 0.
When n= 0, 70+ 2 x 130= 1+ 2= 3 which is a multiple of 3.

Assume that, for some k≥ 0, 7k+ 2 x 13k= 3m for some integer m.
Then 7k+1+ 2 x 3k+ 1= 7(7k)+ 3(2 x 13k= 6(7k)+ 7k+ 12(2 x 13k)+ (2 x 13k)= 3(2(7[sup]k[sup]+ 6(2 x 13k)+ (7k+ 2 x 13k)= 3(2(7[sup]k[sup]+ 6(2 x 13k)+ 3m which is a multiple of 3.

Which all have me soooo confused. Is it my understanding of how proof by induction works that is making me go off?
It would be more possible for me to think around it if it wasn't a proof by induction, but these have me having no clear idea of where to go.
I do have some working out, but they are definitely not worth any attention for now at least.

Please don't give me the answers, since I have a limited number of these questions, but maybe a pointer in the right direction or something would be great!
Thanks!

3. ## Re: More Inductive Proof Questions

Let's start with the intuition of a proof by induction. We want to prove that a proposition is true for every natural number n, called P(n). If P(1) is true and if P(k+1) is true whenever P(k) is true, then P(1) is true obviously, but so is P(2) because 2 = 1 + 1, and thus P(3) is true because 3 = 2 + 1, and the whole row of dominoes falls. That is the intuition.

Being a bit more formal we say

Let S be the set of natural numbers for which P is true. At this point, S may be the empty set.

We prove P(1), which shows that S is not empty. We now say consider k, an arbitrary member of S. All we know about k is that it is a natural number $\ge$ 1 and that P(k) is true. (We know that k exists because S is not empty, and we know that P(k) is true because P is true for every member of S.)

We now prove that P(k + 1) is true. This requires us to reduce P(k + 1) to a true statement in terms of P(k) and k + 1.

As Halls points out, there is absolutely nothing that requires P to be about addition.