Results 1 to 5 of 5

Math Help - Divisibility Proofs

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    140

    Divisibility Proofs

    I think I have this one right. Can anyone help confirm if I've solved this correctly?

    Many thanks.

    Q. 13n - 6n-2 is divisible by 7 for n \in \mathbb{N}_0

    Attempt: Step 1: For n = 1,
    131 - 61-2 = 13 - 6-1 = 13 - 0.166 = 12.833, which cannot be divided by 7.
    However, if n = n + 1: 13n - 6n-2 = 13n+1 - 6n-1
    Now, for n = 1,
    132 - 60 = 169 - 1 = 168, which can be divided by 7.

    Step 2:
    Assume the statement is true for n = k,
    i.e. assume 13k+1 - 6k-1 can be divided by 7
    13k+1 - 6 k-1 = 7Z, where Z is an integer...1
    We must now show that the statement is true for n = k + 1,
    i.e. 13k+2 - 6 can be divided by 7.
    13k+2 - 13(6k-1) + 13(6k-1) - 6k = 13(13k+1 - 6k-1) - 6k-1(6 - 13)...from 1 above = 13(7Z) - (-7)(6k-1) = 91Z + 7(6k-1) = 7[13Z + 6k-1], which can be divided by 7.

    Therefore, the statement is true for n = k + 1, assuming it is true for n = k.
    Thus the statement is true for n = 2, 3... & all n \in \mathbb{N}_0
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Divisibility Proofs

    Slight error with your induction step - if n = k, then 13^k - 6^{k-2} \equiv 0 (\mod 7). I think you replaced k with k+1 or something. Also, n = 2 yields 168.

    Assuming the n = k case is true, you can show that n = k+1 works by showing that

    (13^{k+1} - 6^{k-1}) - (13^{k} - 6^{k-2}) \equiv 0 (\mod 7), and proceed from there.

    ------------------------

    A simpler solution would be to write 13^n \equiv (-1)^n (\mod 7) and 6^{n-2} \equiv (-1)^{n-2} (\mod 7). Then our expression is equivalent to

    (-1)^n - (-1)^{n-2} (\mod 7)

    Clearly, if n is odd or n is even, by substitution we obtain 0 mod 7, and we're done.
    Last edited by richard1234; August 18th 2012 at 08:31 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Divisibility Proofs

    some technical fusses:

    n is never equal to n+1, if you want to consider something equal to n+1, you should write:

    n' = n+1, or something similar.

    since the statement does not hold for n = 0, OR n = 1, it does not hold for \mathbb{N}}_0. it holds for \mathbb{N}_0 - \{0,1\}, or:

    "all natural numbers ≥ 2". mathematical statements should be true. one tiny exception can have devastating results.

    you're missing a "k" in the exponent after the 6 in your statement of the n = k+1 case. this is probably just a typo, but someone will read your proof, you want it to make sense.

    i would add this equation at the start of your proof of the n = k+1 case:

    13k+2 - 6k = 13k+2 - 13(6k-1) + 13(6k-1) - 6k

    again, your concluding statement is not quite correct, it should probably end with: "....and therefore for all n ≥ 2 in \mathbb{N}_0."

    other than that, it looks good.

    EDIT: in light of richard1234's comments, yes: he is correct, if you are now inducting over n' = n+1, your statements should reflect this:

    "for the n' = k case: ...."

    "for the n' = k+1 case: ...."

    *********

    if you are being asked to give an induction proof, then i suppose you will have to give an induction proof. if you are proving something "by hook or by crook" (that is, you can use any method that works), then modular arithmetic *can* simplify things. the key observation here, is that (mod 7) 13 and 6 are the same number: -1.
    Last edited by Deveno; August 18th 2012 at 08:42 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    Great. Thank you very much!!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,802
    Thanks
    687

    Re: Divisibility Proofs

    Hello, GrigOrig99!

    13^n - 6^{n-2}\,\text{ is divisible by 7 for }n \ge 2.

    This can be written

    . . S(n)\!:\;13^{n+1} - 6^{n-1}\,\text{ is divisible by 7 for }n \in N.


    \text{Verify }S(1)\!:\;13^2 - 6^0 \:=\:169 - 1 \:=\:168 \:=\:7\cdot24\;\hdots \text{ True.}

    \text{Assume }S(k)\!:\;13^{k+1} - 6^{k-1} \:=\:7a\,\text{ for some integer }a.


    \text{We must prove that }\,13^{k+2} - 6^k\,\text{ is multiple of 7.}


    \text{We have: }\:13^{k+2} - 6^k

    . . . . . =\;13\!\cdot\!13^{k+1} - 6^k

    . . . . . =\;(7+6)13^{k+1} - 6^k

    . . . . . =\;7\!\cdot\!13^{k+1} + 6\!\cdot\!13^{k+1} - 6^k

    . . . . . =\;7\!\cdot\!13^{k+1} + 6\!\cdot\!13^{k+1} - 6\cdot6^{k-1}

    . . . . . =\;7\!\cdot\!13^{k+1} + 6\underbrace{\left(13^{k+1} - 6^{k-1}\right)}_{\text{This is }7a}
    . . . . . =\;7\!\cdot\!13^{k+1} + 6(7a)

    . . . . . =\;7\left(13^{k+1} + 6a\right)


    \text{Hence, }13^{k+2} - 6^k\text{ is a multiple of 7.}

    \text{The inductive proof is complete.}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 11
    Last Post: August 5th 2012, 11:04 AM
  2. Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 9
    Last Post: July 18th 2012, 11:51 AM
  3. Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: July 16th 2012, 10:17 AM
  4. Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: July 7th 2012, 09:22 AM
  5. Proofs of rules of divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 24th 2010, 10:47 AM

Search Tags


/mathhelpforum @mathhelpforum