Proof by Induction

KIVES

Prove that 5^n - 4n - 1 is always divisible by 16
I tried to do this problem in 3 steps ie...
STEP1: Prove that it is true for n=1
Yet P(1) is NOT true - 5^1 - 4(1) - 1 is NOT divisible by 16. It's true for n=2 and upwards. But I moved on regardless...
STEP2: Assume that it is true for n=k
P(K) - 5^k - 4K - 1 is divisible by 16
STEP3: Prove that it is true for n=k+1
P(K+1) - 5^k+1 - 4(K+1) - 1
=5^k+1 - 4K- 4 - 1
=5.5^k - 4K - 4 - 1
I'm not totally sure I'm right up to this point but the next stage has me demented...I'm trying to get (5^k - 4K - 1) out of this as I assumed in STEP 2 that this part was divisible by 16...
=5.5^k - 5.4k + 5.4k - 5(-4) - 5(-1)
Alright I can extract 5(5^k - 4K - 1) from this but I'm not sure what to do with the 5.4K - 20
In fairness, the whole thing may be flawed, so not altogether sure whether I'm close in the last few lines...multiplying the -4k by 5 and then adding 5(4k) seems to be in keeping with the rules...
Got this from 1990's edition of Text&Tests 4 but found it handier to follow the sample solutions on Mathsireland website.The examples in Texts&Tests 4 seem to be unnecessarily convoluted to somebody who is not a natural born Math's genius...
Any 'simple' explanations would be appreciated...

mahblah

For step 3 you get:



[latex]
5^{k+1}-4(k+1)-1
[/latex]

[latex]
5.5^k-4k-5
[/latex]

[latex]
5.5^k-4k-5-16k+16k
[/latex]

[latex]
5.5^k-20k-5+16k
[/latex]

[latex]
5(5^k-4k-1)+16k
[/latex]

The bracketed part was assumed to be divisible by 16 in step 2, and 16k is divisible by 16.
I hope this is right

Davidius

Firstly it is actually true for n = 1, the result 5 - 4 - 1 = 0 is divisible by 16 as 0/16 is an integer/leaves no remainder.

The problem here is that you appear to have misunderstood the introduction of the -5.4k + 5.4k terms. You are not multiplying -4k by 5 then adding 5.4k, this produces an expression with a different meaning so it's not valid.

5.5^k - 4k - 4 - 1 actually becomes
5.5^k - 5.4k + 5.4k - 4k - 4 - 1. Notice how the -4k term remains, it has not been multiplied by 5.

The reason this is valid is because -5.4k + 5.4k = 0, so by adding those two terms you have just added 0 to the expression, hence nothing has changed. By adding a term 5.4k and then subtracting it, we have effectively done nothing to change the meaning of the expression. Similarly if you multiplied the expression by 5, and divided it by 5 then you won't have changed the expression.

However if I multiply one of the terms by 5 then I have changed the expression unless I also divide the same term by 5. Similarly if I add the term 5.4k to the expression and don't subtract it, then the expression has also been changed.

KIVES

Thanks to Mahblah and Davidus for the correct interpretation. Just come from helping a guy out with the Pass Course earlier this year and decided I'd have a go at the Higher Level syllabus in my spare time. It's little things like not remembering that 0/16 is divisible that catch you out (although having read Davidus' explanation, my memory cells faintly recalled such a fact from bygone days). That and the realization, that unlike Ordinary Level (for the most part), one size does not fit all on the Higher Level course. I know it's a cliche but the need to think on your feet and be constantly aware of why your actually applying some procedure is paramount, rather than just blind execution.
Anyway, enough of the philosophising...thanks again for the help.