Results 1 to 3 of 3

Math Help - Divisible by 9

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    Divisible by 9

    Using mathematical induction, prove

    10^n + 3\cdot4^{n+2} + 5 is div. by 9 \forall \ \mathbb{Z} \ \ n \geq 1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Ideasman View Post
    Using mathematical induction, prove

    10^n + 3\cdot4^{n+2} + 5 is div. by 9 \forall \ \mathbb{Z} \ \ n \geq 1
    okie dokie, let's see where we get with this. i suppose you know the method of induction, so i won't explain it. let's just jump in



    Let P(n): " 9|(10^n + 3 \cdot 4^{n + 2} + 5) for all n \in \mathbb{N}"

    Clearly P(1) is true, since 10 + 3 \cdot 4^3 + 5 = 207 = 9(23)

    So assume P(n) holds for some n \ge 1. That is, we can write P(n) = 9k for some k \in \mathbb{Z}. We show P(n + 1)

    Now P(n + 1) is 10^{n + 1} + 3 \cdot 4^{n + 3} + 5. We must show that this is divisible by 9, provided P(n) is.

    Note that:

    10^{n + 1} + 3 \cdot 4^{n + 3} + 5 = 10^{n + 1} ~\underbrace{+ 10 \cdot 3 \cdot 4^{n + 2} + 10 \cdot 5 - 10 \cdot 3 \cdot 4^{n + 2} - 10 \cdot 5}_{\mbox{Note that this is zero}}~+ 3 \cdot 4^{n + 3} + 5

    = 10( \underbrace{10^n + 3 \cdot 4^{n + 2} + 5}_{\mbox{This is } P(n)}) - 18 \cdot 4^{n + 2} - 45

    = 10 \cdot 9k - 9(2 \cdot 4^{n + 2} + 5)

    = 9(10k - 2 \cdot 4^{n + 2} - 5)

    Since (10k - 2 \cdot 4^{n + 2} - 5) is an integer, we have that 9 | P(n + 1), as desired.

    Thus, P(n) holds for all n \in \mathbb{N} by induction.

    QED
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,864
    Thanks
    744
    Hello, Ideasman!

    Another approach . . .


    Using mathematical induction, prove:

    . . 10^n + 3\cdot4^{n+2} + 5 is divisible by 9,\quad \forall\:n \in \mathbb{N}
    Verify S(1)\!:\;\;10 + 3\!\cdot\!4^3 + 5 \:=\:207 \:=\:9(23) . . . true!


    Assume S(k) is true: . 10^k + 3\!\cdot\!4^{k+2} + 5 \;=\;9a\;\text{ for some integer }a


    Add 9\!\cdot\!10^k + 9\!\cdot\!4^{k+2} to both sides:

    . . 10^k \:{\color{blue}+\: 9\!\cdot\!10^k} + 3\!\cdot\!4^{k+2} \:{\color{blue}+\: 9\!\cdot\!4^{k+2}} + 5 \;=\;9a \:{\color{blue}+ \:9\!\cdot\!10^k + 9\!\cdot\!4^{k+2}}

    . . . . 10^k(1 + 9) + 3\!\cdot\!4^{k+2}(1 + 3) + 5 \;=\;9\underbrace{(a + 10^k + 4^{k+2})}_{\text{some integer }b}
    . . . . . . . . . . . 10^{k+1} + 3\!\cdot\!4^{k+3} + 5 \;=\;9b


    We have proved S(k\!+\!1) . . . The inductive proof is complete.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: February 20th 2013, 10:32 AM
  2. Divisible by 9
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: August 17th 2011, 03:48 AM
  3. Replies: 8
    Last Post: July 3rd 2011, 04:55 PM
  4. Replies: 1
    Last Post: May 8th 2010, 12:49 AM
  5. Replies: 5
    Last Post: January 1st 2010, 02:59 AM

Search Tags


/mathhelpforum @mathhelpforum