Results 1 to 3 of 3

Thread: Induction

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    13

    Induction

    I have the question prove by induction that 5^2n-4^n is divisible by 7.

    In proving p(n+1) implies P(n) I have got:

    (5^2n-4^n)+ 21(5^2n-4^n) is divisible by 7 by inductive hypothesis and since 21 is divisible by 7

    Just wondering if this argument holds or if anyone has any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by iwish123 View Post
    I have the question prove by induction that 5^2n-4^n is divisible by 7.

    In proving p(n+1) implies P(n) I have got:

    (5^2n-4^n)+ 21(5^2n-4^n) is divisible by 7 by inductive hypothesis and since 21 is divisible by 7

    Just wondering if this argument holds or if anyone has any ideas?
    "p(n+1) implies P(n)" is backwards, should read "p(n) implies p(n+1)"

    This is how my inductive step went:

    $\displaystyle 5^{2(n+1)}-4^{n+1}=25\cdot5^{2n}-4\cdot4^n\equiv4\cdot5^{2n}-4\cdot4^n\equiv4(5^{2n}-4^n)\equiv0\ \text{(mod }7\text{)}\$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    4
    Quote Originally Posted by iwish123 View Post
    I have the question prove by induction that 5^2n-4^n is divisible by 7.

    In proving p(n+1) implies P(n) I have got:

    (5^2n-4^n)+ 21(5^2n-4^n) is divisible by 7 by inductive hypothesis and since 21 is divisible by 7

    Just wondering if this argument holds or if anyone has any ideas?
    P(k)

    $\displaystyle 5^{2k}-4^k$ is divisible by 7

    P(k+1)

    $\displaystyle 5^{2(k+1)}-4^{k+1}$ is also divisible by 7.

    You can attempt to prove that $\displaystyle 5^{2k}-4^k$ being divisible by 7 causes $\displaystyle 5^{2k+2}-4^{k+1}$ to be divisible by 7.

    This then means that if your formula is true for some n=k, it's automatically true for the next n=k+1.

    Hence, if it's then true for n=1, it's true for n=2, 3, 4, 5, 6, 7, 8, to infinity.

    $\displaystyle 5^25^{2k}-(4)4^k=(25)5^{2k}-(4)4^k$

    We write this "in terms of" $\displaystyle 5^{2k}-4^k$ to get

    $\displaystyle (21+4)5^{2k}-(4)4^k=(21)5^{2k}+4\left(5^{2k}-4^k\right)$

    Hence, if $\displaystyle 5^{2k}-4^k$ really is divisible by 7,

    then, since 21 is (7)3

    $\displaystyle 5^{2(k+1)}-4^{k+1}$ will also be divisible by 7.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: Apr 21st 2011, 12:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 11th 2010, 02:08 AM
  3. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Mar 19th 2008, 05:12 PM

Search Tags


/mathhelpforum @mathhelpforum