# Proving a statement by Induction

• Apr 19th 2011, 10:08 PM
Oiler
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 :D
• Apr 19th 2011, 11:11 PM
FernandoRevilla
Quote:

Originally Posted by Oiler
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.
• Apr 20th 2011, 02:57 AM
Quote:

Originally Posted by Oiler
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 :D

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) ?