Results 1 to 14 of 14

Math Help - How to show this?

  1. #1
    Member
    Joined
    May 2009
    Posts
    99

    How to show this?

    Show that 3^{2n} - 8n - 1 is divisible by 64 for integer n > 1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121
    Quote Originally Posted by mark1950 View Post
    Show that 3^{2n} - 8n - 1 is divisible by 64 for integer n > 1
    I suggest "proof by induction". If n= 2, we have 3^4- 16- 1= 81- 17= 64 which is obviously divisible by 64.

    Now, assume that, for some k, 3^{2k}- 8k- 1 is divisible by 64. That is, that 3^{2k}- 8k- 1= 64m for some integer m. Now look at 3^{2(k+1)}- 8(k+1)-1= 9(3^{2k})- 8k -8- 1 = 3^{2k}- 8k- 1- 8+ 8(3^{2k})= 64m- 8+ 8(3^{2k})= 64m- 8(3^{2k}-1). Now that is obviously divisible by 8 but 64? You would have to prove that 3^{2k}- 1 is divisible by 8. That is 9^k- 1. Is 1 less than a power of 9 always divisible by 8? 9- 1= 8, 81- 1= 80= 8(10), 729- 1= 728= 8(91), ...

    Hmmm, looks like another proof by induction! As above it works for n= 1. Suppose that 9^k- 1= 8j for some integers k and j. Then 9^{k+1}- 1= 9(9^k)- 1= 8(9^k)+ 9^k- 1= 8(9^k)+ 8j= 8(9^k+ j). Yes! That completes the proof!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    99
    Wow!

    How did you get from
    <br />
9(3^{2k})- 8k -8- 1<br />

    to
    <br />
= 3^{2k}- 8k- 1- 8+ 8(3^{2k})<br />
?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, mark1950!

    Another inductive proof . . .


    Show that 3^{2n} - 8n - 1 is divisible by 64 for integer n > 1
    Verify S(1)\!:\;\;3^2 - 8(1) - 1 \:=\:0, which is divisible by 64.

    Assume S(k)\!:\;\;3^{2k} - 8k - 1 \:=\:64a\:\text{ for some integer }k.


    Add 8\cdot3^{2k} - 8 to both sides:

    . . . 3^{2k} {\color{blue}+ \:8\cdot 3^{2k}} - 8k\: {\color{red} -\: 8} - 1 \;=\;8a {\color{blue}\:+\: 8\cdot 3^{2k}} {\color{red}\:-\:8}

    . . (8 + 1)\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8

    . . . . . . 9\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8

    . . . . . 3^2\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8

    . . . . . . 3^{2k+2} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8

    . . . . . 3^{2(k+1)} - 8(k+1) - 1 \;=\;8\left(a + 3^{2k} - 1\right)\quad\leftarrow\:\text{ multiple of 8}


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

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member pankaj's Avatar
    Joined
    Jul 2008
    From
    New Delhi(India)
    Posts
    317
    Quote Originally Posted by mark1950 View Post
    Show that 3^{2n} - 8n - 1 is divisible by 64 for integer n > 1
    Very Easy.

    9^n-8n-1=(1+8)^n-8n-1

     <br />
(1+8)^n=\binom{n}{0}+\binom{n}{1}8+\binom{n}{2}8^2  +\binom{n}{3}8^3+\binom{n}{4}8^4+........+\binom{n  }{n}8^n<br />

     <br />
9^n=1+8n+8^2\left(\binom{n}{2}+\binom{n}{3}8+\bino  m{n}{4}8^2+........+\binom{n}{n}8^{n-2}\right)<br />

     <br />
3^{2n}-8n-1=64\left(\binom{n}{2}+\binom{n}{3}8+\binom{n}{4}8  ^2+........+\binom{n}{n}8^{n-2}\right)<br />

    Q.E.D
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2009
    Posts
    99
    Quote Originally Posted by Soroban View Post
    Hello, mark1950!

    Another inductive proof . . .


    Verify S(1)\!:\;\;3^2 - 8(1) - 1 \:=\:0, which is divisible by 64.

    Assume S(k)\!:\;\;3^{2k} - 8k - 1 \:=\:64a\:\text{ for some integer }k.


    Add 8\cdot3^{2k} - 8 to both sides:

    . . . 3^{2k} {\color{blue}+ \:8\cdot 3^{2k}} - 8k\: {\color{red} -\: 8} - 1 \;=\;8a {\color{blue}\:+\: 8\cdot 3^{2k}} {\color{red}\:-\:8}

    . . (8 + 1)\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8

    . . . . . . 9\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8

    . . . . . 3^2\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8

    . . . . . . 3^{2k+2} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8

    . . . . . 3^{2(k+1)} - 8(k+1) - 1 \;=\;8\left(a + 3^{2k} - 1\right)\quad\leftarrow\:\text{ multiple of 8}


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

    How did you get
    8\cdot3^{2k} - 8?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member great_math's Avatar
    Joined
    Oct 2008
    Posts
    132
    Quote Originally Posted by mark1950 View Post
    Show that 3^{2n} - 8n - 1 is divisible by 64 for integer n > 1
    P(2) is true

    Assume P(k) is true or 3 ^{2k}-8k-1=64R

    \Rightarrow 3^{2k}=64R+8K+1-------------------(1)

    P(k+1)=3^{2k+2}-8k-8-1

    \Rightarrow P(k+1)=3^{2k}\cdot9-8k-9

    \Rightarrow P(k+1)=9(64R+8k+1)-8k-9 [From 1]

    \Rightarrow P(k+1)=64R\times9+72k+9-8k-9

    \Rightarrow P(k+1)=64R\times9+64k

    \Rightarrow P(k+1)=64(9R+k)=64a

    So 3^{2n} - 8n - 1 is divisible by 64 for integer n > 1
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2009
    Posts
    99
    Quote Originally Posted by great_math View Post
    P(2) is true

    Assume P(k) is true or 3 ^{2k}-8k-1=64R

    \Rightarrow 3^{2k}=64R+8K+1-------------------(1)

    P(k+1)=3^{2k+2}-8k-8-1

    \Rightarrow P(k+1)=3^{2k}\cdot9-8k-9

    \Rightarrow P(k+1)=9(64R+8k+1)-8k-9 [From 1]

    \Rightarrow P(k+1)=64R\times9+72k+9-8k-9

    \Rightarrow P(k+1)=64R\times9+64k

    \Rightarrow P(k+1)=64(9R+k)=64a

    So 3^{2n} - 8n - 1 is divisible by 64 for integer n > 1
    Hmm. I understood everything except for the last part. How did u got 64a? How did 64(9R + k) becomes 64a?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member great_math's Avatar
    Joined
    Oct 2008
    Posts
    132
    Quote Originally Posted by mark1950 View Post
    Hmm. I understood everything except for the last part. How did u got 64a? How did 64(9R + k) becomes 64a?
    64\times(9R+k)=64a where a=(9R+k)
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    May 2009
    Posts
    99
    Hmm...but how does that show that  3^{2n} - 8n - 1 is divisible by 64 for integer n > 1?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    May 2009
    Posts
    527
    When great math wrote 64(9R + k) = 64a, I'm guessing that he/she's just saying that P(k + 1) simplifies to 64 times some number, which he/she decided to call a. That's all.


    01
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member great_math's Avatar
    Joined
    Oct 2008
    Posts
    132
    Quote Originally Posted by yeongil View Post
    When great math wrote 64(9R + k) = 64a, I'm guessing that he/she's just saying that P(k + 1) simplifies to 64 times some number, which he/she decided to call a. That's all.


    01
    Yes thats right!
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    May 2009
    Posts
    99
    Oh...so when the answer has 64 in it after doing the mathematical induction it is safe to say that it is proven already, right?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by mark1950 View Post
    Oh...so when the answer has 64 in it after doing the mathematical induction it is safe to say that it is proven already, right?
    Please learn something from your other thread: http://www.mathhelpforum.com/math-he...sible-7-a.html
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Using the MVT to show this
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 25th 2010, 11:19 AM
  2. Show the sum
    Posted in the Calculus Forum
    Replies: 5
    Last Post: October 21st 2010, 03:28 AM
  3. Show that f o g is one-to-one
    Posted in the Calculus Forum
    Replies: 2
    Last Post: January 24th 2010, 06:29 PM
  4. Show that ln5 < 1 + 1/2 + 1/3 + 1/4.
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 6th 2009, 01:29 AM
  5. how to show show this proof using MAX
    Posted in the Calculus Forum
    Replies: 2
    Last Post: January 14th 2009, 12:05 PM

/mathhelpforum @mathhelpforum