Results 1 to 3 of 3

Thread: More Inductive Proof Questions

  1. #1
    Newbie ACARROT's Avatar
    Joined
    Jun 2017
    From
    Australia
    Posts
    4

    Angry 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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,109
    Thanks
    2802

    Re: More Inductive Proof Questions

    Quote Originally Posted by ACARROT View Post
    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!
    Last edited by HallsofIvy; Jul 23rd 2017 at 03:56 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Feb 2014
    From
    United States
    Posts
    1,705
    Thanks
    802

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. More Inductive Proof Questions
    Posted in the Math Philosophy Forum
    Replies: 0
    Last Post: Jul 13th 2017, 06:32 PM
  2. help me with Inductive Proof #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 16th 2009, 10:16 AM
  3. Inductive Questions, final algebra part
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 15th 2009, 07:02 PM
  4. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: Oct 7th 2009, 01:09 PM
  5. help...inductive proof???
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 16th 2008, 04:11 PM

Search Tags


/mathhelpforum @mathhelpforum