- #1
GregA
- 210
- 0
I am trying to get myself better at writing proofs and for one of the easier (I assume) exercises that contain no back of the book solutions I'm asked to prove by induction on n that:
For every positive integer n, 3 divides 4^n + 5
Before I show my attempt I want to say that my reason for posting is because I seem to have walked a thousand miles just to cross the road with this one, and my way just looks ugly. (Not even sure if I've actually used induction) If anyone could give me a few pointers so that I can reach something far simpler I'd be very grateful.
My attempt:
Let 4^n + 5 = 3p for some integer p.
Firstly I show that the expression holds for n = 1
4^0 +5 = 6 = 3(2) This is okay and since n > 0 then p>2
Now to show that if it holds for 4^k + 5 it holds for 4^{k+1} + 5
So let's assume it does hold for 4^k + 5..
then 4^k + 5 = 3q for some integer q \Rightarrow 4^k = 3q - 5
If it works for k, then it works for k+1 such that 4^{k+1} = 4(3q -5)
and as 4^{k+1} > 4^k > 4^0 \Rightarrow q > p > 2
4^{k+1} - 1 = 12q -21 = 3(4q-7)
4^{k+1} -1 = (2^{2(k+1)} - 1 = (2^{k+1} +1)(2^{k+1} - 1)
I now have to show that if either of those two brackets contains a number that is a multiple of 3 then both sides are divisible by 3...and I think this also has to be proven
My attempt at proving that either (2^{k+1} +1) or (2^{k+1} - 1) = 3p for some integer p:
Firstly as 2^x does not contain 3 as a factor then it is not a multiple of 3 (<---My attempt at proving that is a bit rubbish) and so assuming this for now I'll make the statement:
For any integer n \neq 3q 3q = n+1 or n-1
Assume this is false, ie: that if n \neq 3q, 3q \neq n+1 or 3q \neq n-1 and let n - 1 = m such that:
3q \neq m, 3q \neq m+1 or 3q \neq m+2 then:
3q = m+3 or m+4 or m+5...m+x but if 3q = m+3 then 3(r - 1) = m but if (r-1) = q, m \neq 3q! and if 3q = m+4 then 3(s + 1) = m and so on...it follows that no integer can ever be a multiple of 3...Therefore the original assumption was false and that :
For any integer n \neq 3q 3q = n+1 or n-1
by returning to the first problem I have to prove that
(2^{k+1} +1)(2^{k+1} - 1) = 12q -21 = 3(4q-7)
if I let (2^{k+1} +1)(2^{k+1} - 1) = (n+1)(n-1) then since one of these is a multiple of three...the expression 4^{k+1} + 5 is divisible by 3 and is equal to 3(4q-7) and since q>2 we have a positive integer...which is about as far as I can take this...
What hole exist in the above and am I right in thinking that there was a much easier way of reaching a solution?
For every positive integer n, 3 divides 4^n + 5
Before I show my attempt I want to say that my reason for posting is because I seem to have walked a thousand miles just to cross the road with this one, and my way just looks ugly. (Not even sure if I've actually used induction) If anyone could give me a few pointers so that I can reach something far simpler I'd be very grateful.
My attempt:
Let 4^n + 5 = 3p for some integer p.
Firstly I show that the expression holds for n = 1
4^0 +5 = 6 = 3(2) This is okay and since n > 0 then p>2
Now to show that if it holds for 4^k + 5 it holds for 4^{k+1} + 5
So let's assume it does hold for 4^k + 5..
then 4^k + 5 = 3q for some integer q \Rightarrow 4^k = 3q - 5
If it works for k, then it works for k+1 such that 4^{k+1} = 4(3q -5)
and as 4^{k+1} > 4^k > 4^0 \Rightarrow q > p > 2
4^{k+1} - 1 = 12q -21 = 3(4q-7)
4^{k+1} -1 = (2^{2(k+1)} - 1 = (2^{k+1} +1)(2^{k+1} - 1)
I now have to show that if either of those two brackets contains a number that is a multiple of 3 then both sides are divisible by 3...and I think this also has to be proven
My attempt at proving that either (2^{k+1} +1) or (2^{k+1} - 1) = 3p for some integer p:
Firstly as 2^x does not contain 3 as a factor then it is not a multiple of 3 (<---My attempt at proving that is a bit rubbish
) and so assuming this for now I'll make the statement:For any integer n \neq 3q 3q = n+1 or n-1
Assume this is false, ie: that if n \neq 3q, 3q \neq n+1 or 3q \neq n-1 and let n - 1 = m such that:
3q \neq m, 3q \neq m+1 or 3q \neq m+2 then:
3q = m+3 or m+4 or m+5...m+x but if 3q = m+3 then 3(r - 1) = m but if (r-1) = q, m \neq 3q! and if 3q = m+4 then 3(s + 1) = m and so on...it follows that no integer can ever be a multiple of 3...Therefore the original assumption was false and that :
For any integer n \neq 3q 3q = n+1 or n-1
by returning to the first problem I have to prove that
(2^{k+1} +1)(2^{k+1} - 1) = 12q -21 = 3(4q-7)
if I let (2^{k+1} +1)(2^{k+1} - 1) = (n+1)(n-1) then since one of these is a multiple of three...the expression 4^{k+1} + 5 is divisible by 3 and is equal to 3(4q-7) and since q>2 we have a positive integer...which is about as far as I can take this...
What hole exist in the above and am I right in thinking that there was a much easier way of reaching a solution?
Last edited:
...I am still learning the ropes!
whilst trying to find out why I'm talking BS I figured out that if we say that k = 0 then...it does work for k+1!... and then for k+2...! 
