Results 1 to 7 of 7

Math Help - Is this proof by induction set out well?

  1. #1
    Member alexgeek's Avatar
    Joined
    Mar 2010
    From
    Wales, UK
    Posts
    77

    Is this proof by induction set out well?

    Just wanted to check that this proof is set out correctly and that the last statement is logically correct:

    Question

    Use mathematical induction to prove that 4^{2n}-1 is divisible by 15 for all positive integers n.
    Answer
    Let P be 4^{2n}-1 is divisible by 15.
    Assuming u_n = 4^{2n}-1 to be true [1] ( u_n = 15k),
    u_{n+1} = 4^{2(n+1)} -1 = 4^{2n+2} - 1
    u_{n+1} = 16 \times 4^{2n} - 1
    From [1], u_{n+1} = 16(u_n + 1) -1
    u_{n+1} = 16(15k + 1) -1
     u_{n+1} = 16(15k)+ 16 -1 = 16(15k) - 15 = 15(16k-1)
    Therefore if u_n is divisible by 15, then so is u_{n+1},
    When n =1 , u_n = 4^{2 \times 1} -1 = 15. Therefore the basis case holds true.
    Therefore by mathematical induction,
      \forall n \in \mathbb{Z} , u_n \implies u_{n+1}, u_n \therefore P
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,548
    Thanks
    1418

    Re: Is this proof by induction set out well?

    Quote Originally Posted by alexgeek View Post
    Just wanted to check that this proof is set out correctly and that the last statement is logically correct:

    Question


    Answer
    Base step: \displaystyle n = 1

    \displaystyle \begin{align*} 4^{2n} - 1 &= 4^{2\cdot 1} - 1 \\ &= 4^2 - 1 \\ &= 16 - 1 \\ &= 15 \end{align*}

    which is divisible by \displaystyle 15.


    Inductive step: Assume \displaystyle 4^{2k} - 1 = 15m (i.e. it's divisible by \displaystyle 15)

    Let \displaystyle n = k + 1

    \displaystyle \begin{align*} 4^{2n} - 1 &= 4^{2(k + 1)} - 1\\ &= 4^{2k + 2} - 1 \\ &= 4^{2k}4^2 - 1 \\ &= (15m + 1)4^2 - 1 \\ &= 4^2\cdot 15m + 4^2 - 1 \\ &= 4^2\cdot 15m + 16 - 1\\ &= 4^2\cdot 15m + 15 \\ &= 15(4^2 \cdot m + 1) \end{align*}

    which is divisible by \displaystyle 15.


    Therefore \displaystyle 4^{2n} - 1 is divisible by \displaystyle 15 for all positive integer \displaystyle n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member alexgeek's Avatar
    Joined
    Mar 2010
    From
    Wales, UK
    Posts
    77

    Re: Is this proof by induction set out well?

    That seems more clear thanks. Would you advise against writing is symbolically?

    btw, I think you have to change the tags in your sig.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1

    Re: Is this proof by induction set out well?

    Quote Originally Posted by alexgeek View Post
    Just wanted to check that this proof is set out correctly and that the last statement is logically correct:

    Question


    Answer
    You could shorten your proof considerably by writing

    u_n=4^{2n}-1

    u_{n+1}=4^{2(n+1)}-1=4^{2n+2}-1=(16)4^{2n}-1=(15)4^{2n}+4^{2n}-1

    \Rightarrow\ u_{n+1}=(15)4^{2n}+u_n

    so that if u_n is a multiple of 15, then u_{n+1} will also be a multiple of 15.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Is this proof by induction set out well?

    Quote Originally Posted by alexgeek View Post
    Would you advise against writing is symbolically?
    Good question. See an example of a proof on p. 9 of "Mathematical Writing" by Knuth, Larrabee, and Roberts (PDF).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member alexgeek's Avatar
    Joined
    Mar 2010
    From
    Wales, UK
    Posts
    77

    Re: Is this proof by induction set out well?

    I was like ooh that looks interesting then saw that it's 112 pages long. I'll keep it until next week when my exams are over.
    Thank you though.

    Edit. Oh you said page 9. Brain is melting from too much maths sorry
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Is this proof by induction set out well?

    Quote Originally Posted by alexgeek View Post
    Just wanted to check that this proof is set out correctly and that the last statement is logically correct:

    Question


    Answer
    Or,

    4^{2n}-1=16^n-1

    16\equiv 1(\mod15)

    Hence, 16^n\equiv 1^n(\mod15).


    16^n\equiv 1=(\mod15) or 4^{2n}\equiv 1(\mod15)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 22nd 2010, 04:18 AM
  2. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  3. proof by induction
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 28th 2009, 08:11 AM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. Proof by Induction?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 24th 2007, 07:57 AM

Search Tags


/mathhelpforum @mathhelpforum