Results 1 to 3 of 3

Thread: More Inductive Proof Questions

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

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

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,415
    Thanks
    2889

    Re: More Inductive Proof Questions

    Quote Originally Posted by ACARROT View Post
    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 x^{n-1}- 1 for n a positive integer". The smallest "positive integer" is 1 and P(1) is " 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 x^{k-1}- 1 is divisible by x- 1. To prove P(k+1) we have to prove that x^{k-1+ 1}- 1= x^k- 1 is divisible by x- 1. Clearly, we want to go from x^k- 1 to [tex]x^{k-1}- 1[tex]. Try writing x^k- 1 as [tex]x(x^{k-1})- 1= 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, 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 3^7= 2187. Yes, 5040> 2187.

    Suppose that, for some k, 1 x 2 x 3 x 4 x .... x k\ge 3^k. Now look at 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, 7^k+ 2(13^k)= 3a for some integer a (so is a multiple of 3). We look at n= k+1. 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!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Feb 2014
    From
    United States
    Posts
    1,741
    Thanks
    808

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

Similar Math Help Forum Discussions

  1. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Dec 8th 2009, 02:11 AM
  2. Inductive Questions, final algebra part
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 15th 2009, 08:02 PM
  3. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: Oct 7th 2009, 02:09 PM
  4. Ugh, another inductive proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 13th 2008, 03:56 PM
  5. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Apr 28th 2008, 07:24 PM

/mathhelpforum @mathhelpforum