Results 1 to 5 of 5

Math Help - Proof validation for number divisible by 25

  1. #1
    Junior Member
    Joined
    Dec 2005
    Posts
    58

    Proof validation for number divisible by 25

    I have to prove that 2^{n + 2}  \cdot 3^n  + 5n - 4 is divisible by 25 for n>0.

    My proof:
    \begin{array}{l}<br />
 2^{n + 2}  \cdot 3^n  + 5n - 4 = 2^n  \cdot 2^2  \cdot 3^n  + 5n - 4 = 6^n  \cdot 4 + 5n - 4 =  \\ <br />
 5n - 4(6^n  - 1) \\ <br />
 \end{array}<br />

    This expression is divisible by 25 for n=1, so we look for n>1.

    6^n is always number which last two digits will be 36,16,96,76,56,36....
    So we can establish now for which value of n will last two digits be for number 6^n.

    k>0
    \begin{array}{l}<br />
 n = 5k - 3,{\rm{    }}6^{5k - 3}  = ....36 \\ <br />
 n = 5k - 2,{\rm{    }}6^{5k - 2}  = ....16 \\ <br />
 n = 5k - 1,{\rm{    }}6^{5k - 1}  = ....96 \\ <br />
 n = 5k,{\rm{         }}6^{5k}     = ....76 \\ <br />
 n = 5k + 1,{\rm{    }}6^{5k + 1}  = ....56 \\ <br />
 \end{array}<br />

    Since we have expression 4(6^n  - 1) then last two digits of that expression will be:

    \begin{array}{l}<br />
 n = 5k - 3,{\rm{    }}4(6^{5k - 3}  - 1) = ....40 \\ <br />
 n = 5k - 2,{\rm{    }}4(6^{5k - 2}  - 1) = ....60 \\ <br />
 n = 5k - 1,{\rm{    }}4(6^{5k - 1}  - 1) = ....80 \\ <br />
 n = 5k,{\rm{         }}4(6^{5k}     - 1) = ....00 \\ <br />
 n = 5k + 1,{\rm{    }}4(6^{5k + 1}  - 1) = ....20 \\ <br />
 \end{array}<br />

    If we now look at whole expression we will get:
    \begin{array}{l}<br />
 n = 5k - 3,{\rm{    }}5(5k - 3) - 4(6^{5k - 3}  - 1) \\ <br />
 n = 5k - 2,{\rm{    }}5(5k - 2) - 4(6^{5k - 2}  - 1) \\ <br />
 n = 5k - 1,{\rm{     }}5(5k - 1) - 4(6^{5k - 1}  - 1) \\ <br />
 n = 5k,{\rm{          }}5(5k) - 4(6^{5k}  - 1) \\ <br />
 n = 5k + 1,{\rm{     }}5(5k + 1) - 4(6^{5k + 1}  - 1) \\ <br />
 \end{array}<br />


    For example lets take first expression too see if its divisible by 25, same proof is for other ones.
    5(5k - 3) - 4(6^{5k - 3}  - 1) = 25k - 15 - .....40
    .....40 means that last two digits of that number is 40. .....40 - 15 have last two digits 25, so we have number 25k + .....25 which is divisible by 25. Same proof is for other numbers.

    Is this proof valid?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,830
    Thanks
    123
    Quote Originally Posted by DenMac21
    I have to prove that 2^{n + 2}  \cdot 3^n  + 5n - 4 is divisible by 25 for n>0.
    ...
    Is this proof valid?
    Hello,

    your proof looks OK to me. When I did this proof for my own (pleasure, of course!) I came to the same result. Here is my way to do it:

    I use "complete induction" (I'm quite certain, that this isn't the correct expression. It's litterally translated from German. Sorry!). You have to use Peano's Axiom about \mathbb{N}.

    1. A(n=1): 2^{1 + 2}  \cdot 3^1  + 5\cdot 1 - 4=24+1\  is\   divisible\   by\  25
    2. A(n): Let 2^{n + 2}  \cdot 3^n  + 5\cdot n - 4\  is\   divisible\   by\  25 be true.
    A(n+1): 2^{n+1 + 2}  \cdot 3^n+1  + 5\cdot(n+ 1) - 4=
    2\cdot 2^{n + 2}  \cdot 3 \cdot  3^n  + 5\cdot n+ 5 - 4=
    6\cdot 2^{n + 2}   \cdot  3^n  + 5\cdot n+ 5 - 4=
    5\cdot 2^{n + 2}   \cdot  3^n   +5+\underbrace{2^{n + 2}   \cdot  3^n+5\cdot n - 4}_{\csub{div.\ by\ 25}}=
    5\cdot \left(2^{n + 2}   \cdot  3^n   +1 \right)+\underbrace{2^{n + 2}   \cdot  3^n+5\cdot n - 4}_{\csub{div.\ by\ 25,\ see \ A(n)}}=
    5\cdot \left(4 \cdot 6^n +1 \right)+\underbrace{2^{n + 2}   \cdot  3^n+5\cdot n - 4}_{\csub{div.\ by\ 25}}=
    All powrs of 6 have as last digit a 6, so the produkt 4*6^n has always a 4 as it's last digit. That means the number in the paranthesis has a 5 as last digit and is therefore divisible by 5. Therefore the 1rst summand is divisible by 25 too. Therefore the complete expression is divisible by 25.

    Now you've proofed that your expression is true for (n+1) if it is true for n. That means: You've proofed, that it is true for n=1.
    Because it is true for n=1 it is true for n=1+1=2 too;
    because it is true for n=2 it is true for n=2+1=3 too;
    because it is true for n=3 it is true for n=3+1=4 too.

    So it is true for all n \in \mathbb{N}

    Maybe this was of some help for you.

    Greetings

    EB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by earboth
    Hello,

    your proof looks OK to me. When I did this proof for my own (pleasure, of course!) I came to the same result. Here is my way to do it:

    I use "complete induction" (I'm quite certain, that this isn't the correct expression. It's litterally translated from German. Sorry!). You have to use Peano's Axiom about \mathbb{N}.

    1. A(n=1): 2^{1 + 2}  \cdot 3^1  + 5\cdot 1 - 4=24+1\  is\   divisible\   by\  25
    2. A(n): Let 2^{n + 2}  \cdot 3^n  + 5\cdot n - 4\  is\   divisible\   by\  25 be true.
    A(n+1): 2^{n+1 + 2}  \cdot 3^n+1  + 5\cdot(n+ 1) - 4=
    2\cdot 2^{n + 2}  \cdot 3 \cdot  3^n  + 5\cdot n+ 5 - 4=
    Shorter route from here is:

    Suppose A(n) is true then consider:

    2^{n+1 + 2}\ 3^{n+1}  + 5(n+ 1) - 4=
    (2^{n+2}\  3^n + 5n -4)6 -30n + 24 +5(n+1) -4=
    (2^{n+2}\ 3^n + 5n -4)6 -25n +25

    But the first term in the last line above is divisible by 25 by hypothesis, and
    the second term is a multiple of 25, so A(n+1) holds, and so it follows
    by mathematical induction that A(n) is true for all n in \mathbb{N_+}

    I must admit that I had been putting off checking DenMac21's proof because
    it looked too long and complicated

    RonL
    Last edited by CaptainBlack; March 16th 2006 at 05:02 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Dec 2005
    Posts
    58
    Quote Originally Posted by CaptainBlack
    Shorter route from here is:

    Suppose A(n) is true then consider:

    2^{n+1 + 2}\ 3^{n+1}  + 5(n+ 1) - 4=
    (2^{n+2}\  3^n + 5n -4)6 -30n + 24 +5(n+1) -4=
    (2^{n+2}\ 3^n + 5n -4)6 -25n +25

    But the first term in the last line above is divisible by 25 by hypothesis, and
    the second term is a multiple of 25, so A(n+1) holds, and so it follows
    by mathematical induction that A(n) is true for all n in \mathbb{N_+}

    I must admit that I had been putting off checking DenMac21's proof because
    it looked too long and complicated

    RonL
    Ye, I admit it looks scary!

    It is long, but its rather simple, I don' think its complicated.

    I must say that I do not know the way of solution that earboth and you gave here.

    "complete induction" , Peano's Axiom is not known to me!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by DenMac21
    Ye, I admit it looks scary!

    It is long, but its rather simple, I don' think its complicated.

    I must say that I do not know the way of solution that earboth and you gave here.

    "complete induction" , Peano's Axiom is not known to me!
    It is bog standard Mathematical Induction, which is usually treated
    as an axiom of arithmetic (probably it is one of Peano's axioms I
    don't recall at this time)

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: August 14th 2011, 03:55 AM
  2. Replies: 8
    Last Post: July 3rd 2011, 03:55 PM
  3. A number divisible by 13,17 or 19
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 21st 2010, 12:47 AM
  4. number divisible
    Posted in the Algebra Forum
    Replies: 3
    Last Post: August 5th 2008, 07:25 PM
  5. Proof validation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 25th 2006, 08:07 AM

Search Tags


/mathhelpforum @mathhelpforum