# Math Help - Simple Induction Problem

1. ## Simple Induction Problem

tried this in so many ways... not getting anywhere, dont know why - fresh ideas helpful.

"Use induction to prove the statement. Identify P(n) explicitly for the statement."
"For all n e N, 4 | ((5^n)-1)"

Use spoiler alerts please, I dont want a full answer, just a nudge in the right direction.

2. ## Re: Simple Induction Problem

Check that the statement is true for some small n (e.g. n = 1, n = 2). Show that if the statement is true for n = k, then it is true for n = k+1.

3. ## Re: Simple Induction Problem

Sorry, I should have specified what I've already attempted. I've made my base case and determined a value for P(1), assumed it to be true using induction hypothesis for P(k), and attempted to show it to be true for P(k+1). However, I never seem able to make P(k+1) true.

hypothesis: P(k) : 4 | ((5^k)-1)

conclusion: P(k+1) : 4 | ((5^(k+1))-1)

after this, i blank. all my methods seem to fail. still need a nudge in the right direction :S

frustrating

5. ## Re: Simple Induction Problem

We know that $4|P(k)$, and we want to show that $4|P(k+1)$.

Hint: find $P(k+1) - P(k)$. Must 4 divide this expression?

6. ## Re: Simple Induction Problem

ahh, touche.

thanks a bunch!

7. ## Re: Simple Induction Problem

Originally Posted by richard1234
We know that $4|P(k)$, and we want to show that $4|P(k+1)$.
No, no, no and NO! P(k) is a property of k, so for each positive integer k, P(k) is either true or false. You can't say that 4 divides true or false! By the way, the problem asks to identify P(n), and the first thing the OP should have done when showing what he/she had already attempted was to write P(n) explicitly.