Results 1 to 3 of 3

Thread: Divisible by 9

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    Divisible by 9

    Using mathematical induction, prove

    $\displaystyle 10^n + 3\cdot4^{n+2} + 5$ is div. by $\displaystyle 9$ $\displaystyle \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

    $\displaystyle 10^n + 3\cdot4^{n+2} + 5$ is div. by $\displaystyle 9$ $\displaystyle \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 $\displaystyle P(n)$: "$\displaystyle 9|(10^n + 3 \cdot 4^{n + 2} + 5)$ for all $\displaystyle n \in \mathbb{N}$"

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

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

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

    Note that:

    $\displaystyle 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$

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

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

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

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

    Thus, $\displaystyle P(n)$ holds for all $\displaystyle 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
    12,028
    Thanks
    848
    Hello, Ideasman!

    Another approach . . .


    Using mathematical induction, prove:

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


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


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

    . . $\displaystyle 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}} $

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


    We have proved $\displaystyle 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: Feb 20th 2013, 09:32 AM
  2. Divisible by 9
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: Aug 17th 2011, 02:48 AM
  3. Replies: 8
    Last Post: Jul 3rd 2011, 03:55 PM
  4. Replies: 1
    Last Post: May 7th 2010, 11:49 PM
  5. Replies: 5
    Last Post: Jan 1st 2010, 01:59 AM

Search Tags


/mathhelpforum @mathhelpforum