Results 1 to 3 of 3

Math Help - Proving a statement by Induction

  1. #1
    Member
    Joined
    Jan 2011
    Posts
    87

    Proving a statement by Induction

    Hey all,

    I have the following statement: 5|7^k-2^k for all k in N

    I want to prove it by induction, so I proceed as follows..
    Basis step:
    let p(k) be the statement that 7^k-2^k = 5m for m in N and k in P.
    Then p(1) is the statement 7^1-2^1=5m for some m in N. This is clearly true for m = 1.
    Induction step:
    Suppose that p(k) is true for some k in P, That is, 7^k-2^k = 5m for some m in N, then, 7^(k+1) - 2^(k+1) = 5*1^(k+1) for k + 1 in N.
    Therefore, p(k+1) is true. Hence p(k) is true for all k in P.

    The basis step is straight forward, but I am not sure whether I have done the induction step correctly particularly with the result 5^(k+1). Any criticism welcome. Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45
    Quote Originally Posted by Oiler View Post
    7^(k+1) - 2^(k+1) = 5*1^(k+1) for k + 1 in N.

    That is not true. At any case, you can easily prove the statement without using induction:


    ( a^{n+1} - b^{n+1} ) = ( a - b ) ( a^n +a^{n-1} b + ... + b^n )

    so,

    ( 7^(k+1) - 2^(k+1) ) = 5 ( ... ) = 5 m with m positive integer.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Oiler View Post
    Hey all,

    I have the following statement: 5|7^k-2^k for all k in N

    I want to prove it by induction, so I proceed as follows..
    Basis step:
    let p(k) be the statement that 7^k-2^k = 5m for m in N and k in P.
    Then p(1) is the statement 7^1-2^1=5m for some m in N. This is clearly true for m = 1.
    Induction step:
    Suppose that p(k) is true for some k in P, That is, 7^k-2^k = 5m for some m in N, then, 7^(k+1) - 2^(k+1) = 5*1^(k+1) for k + 1 in N.
    Therefore, p(k+1) is true. Hence p(k) is true for all k in P.

    The basis step is straight forward, but I am not sure whether I have done the induction step correctly particularly with the result 5^(k+1). Any criticism welcome. Thanks
    Your induction step should be

    P(k)

    5 divides 7^k-2^k


    P(k+1)

    5 divides 7^(k+1)-2^(k+1)


    Try to show that P(k+1) will be true if P(k) is true.

    7^(k+1)-2^(k+1) = (7)7^k-(2)2^k

    =7^k-2^k+(6)7^k-2^k

    =7^k-2^k+7^k-2^k+(5)7^k

    =2(7^k-2^k)+(5)7^k

    Now, if P(k) really is true, what can we say about P(k+1) ?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving a statement is true.
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 25th 2011, 01:13 AM
  2. Need help proving a congruence statement
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 19th 2011, 06:20 PM
  3. Replies: 1
    Last Post: October 18th 2010, 06:43 AM
  4. Help on proving this statement...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 20th 2008, 12:47 PM
  5. Proving Statement True
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 15th 2008, 01:38 AM

Search Tags


/mathhelpforum @mathhelpforum