# Math Help - Prove using induction on n that 3 divides (4^n)+5

1. ## [Solved] Prove using induction on n that 3 divides (4^n)+5

Hi everyone,

First time poster. This is probably an embarrassingly easy problem. I'm a non-maths student working through an intro to proof book in my spare time and there are problem sets with no solutions. I've got stuck on a couple of problems. This is one of them.

Question: Prove by induction on $n$ that, for all positive integers $n$, $3$ divides $4^n +5$.

I know where I need to go with this, I think, I'm just stuck on the inductive step:

Proof: We use induction on n. If $3$ divides $4^n +5$, then $4^n +5=3q$ for some integer $q$.

Base case: If $n=1$, then $4^n +5=9=3q$, where $q=3$, proving the base case.

Inductive step: Suppose as inductive hypothesis that $4^k +5=3q$ for some integer $k$. Then $4^{k+1} +5=3q$ (by inductive hypothesis).

That's as far as I get. Obviously, $4^{k+1} +5=4*4^k +5$ by definition, but I get stuck there.

EDIT: not sure how to add the solved prefix, hope this is an okay ad hoc measure.

2. ## Re: Prove using induction on n that 3 divides (4^n)+5

Originally Posted by TimM
Hi everyone,

First time poster. This is probably an embarrassingly easy problem. I'm a non-maths student working through an intro to proof book in my spare time and there are problem sets with no solutions. I've got stuck on a couple of problems. This is one of them.
Question: Prove by induction on $n$ that, for all positive integers $n$, $3$ divides $4^n +5$.
I know where I need to go with this, I think, I'm just stuck on the inductive step:
Proof: We use induction on n. If $3$ divides $4^n +5$, then $4^n +5=3q$ for some integer $q$.

Base case: If $n=1$, then $4^n +5=9=3q$, where $q=3$, proving the base case.

Inductive step: Suppose as inductive hypothesis that $4^k +5=3q$ for some integer $k$. Then $4^{k+1} +5=3\color{red}x\color{black}$ (by inductive hypothesis). not 3q as written.
That's as far as I get. Obviously, $4^{k+1} +5=4*4^k +5$ by definition, but I get stuck there.

$(4)4^k+5=(3)4^k+4^k+5$

Now if 3 divides $4^k+5$

it will certainly divide $(3)4^k+4^k+5$

So if $4^k+5=3q$, then $(3)4^k+4^k+5=3\left(4^k+q\right)=3x$

3. ## Re: Prove using induction on n that 3 divides (4^n)+5

Originally Posted by TimM
Hi everyone,

First time poster. This is probably an embarrassingly easy problem. I'm a non-maths student working through an intro to proof book in my spare time and there are problem sets with no solutions. I've got stuck on a couple of problems. This is one of them.

Question: Prove by induction on $n$ that, for all positive integers $n$, $3$ divides $4^n +5$.

I know where I need to go with this, I think, I'm just stuck on the inductive step:

Proof: We use induction on n. If $3$ divides $4^n +5$, then $4^n +5=3q$ for some integer $q$.

Base case: If $n=1$, then $4^n +5=9=3q$, where $q=3$, proving the base case.

Inductive step: Suppose as inductive hypothesis that $4^k +5=3q$ for some integer $k$. Then $4^{k+1} +5=3q$ (by inductive hypothesis).

That's as far as I get. Obviously, $4^{k+1} +5=4*4^k +5$ by definition, but I get stuck there.

You need to show that $\displaystyle 4^{k + 1} + 5 = 3r$, since $\displaystyle q$ and $\displaystyle r$ would be different.

Anyway...

\displaystyle \begin{align*} 4^{k + 1} + 5 &= 4\cdot 4^k + 5 \\ &= 4\cdot 4^k + 20 - 15 \\ &= 4(4^k + 5) - 15 \\ &= 4\cdot 3q - 15 \\ &= 3(4q - 5) \\ &= 3r\textrm{ where }r = 4q - 5\end{align*}

4. ## Re: Prove using induction on n that 3 divides (4^n)+5

from where you left

4^(k+1) + 5 = 4 . 4^k + 20 - 15

= 4[ 4^k + 5 ] - 15

= 4 (3q) - 15 => 3[ 4q - 5 ]

which gives required result

5. ## Re: Prove using induction on n that 3 divides (4^n)+5

Originally Posted by TimM
Hi everyone,

First time poster. This is probably an embarrassingly easy problem. I'm a non-maths student working through an intro to proof book in my spare time and there are problem sets with no solutions. I've got stuck on a couple of problems. This is one of them.

Question: Prove by induction on $n$ that, for all positive integers $n$, $3$ divides $4^n +5$.

I know where I need to go with this, I think, I'm just stuck on the inductive step:

Proof: We use induction on n. If $3$ divides $4^n +5$, then $4^n +5=3q$ for some integer $q$.

Base case: If $n=1$, then $4^n +5=9=3q$, where $q=3$, proving the base case.

Inductive step: Suppose as inductive hypothesis that $4^k +5=3q$ for some integer $k$. Then $4^{k+1} +5=3q$ (by inductive hypothesis).

That's as far as I get. Obviously, $4^{k+1} +5=4*4^k +5$ by definition, but I get stuck there.

Without induction:

$4^n + 5=(3+1)^n+5=3t+1+5=3t+6$

6. ## Re: Prove using induction on n that 3 divides (4^n)+5

Originally Posted by Prove It
You need to show that $\displaystyle 4^{k + 1} + 5 = 3r$, since $\displaystyle q$ and $\displaystyle r$ would be different.
Lol, obviously. Sorry.

Anyway, thanks everyone!

7. ## Re: Prove using induction on n that 3 divides (4^n)+5

Hi !
without induction : $4\equiv 1[3]$ so $4^{k}\equiv 1[3]$ knowing that $5\equiv 2[3]$ by adding we get the result

8. ## Re: Prove using induction on n that 3 divides (4^n)+5

I don't see the point of giving non-induction answers to questions that clearly state
to answer using Proof By Induction.
Who would answer using a different method if an exam question began
"Prove, by induction........" ?

9. ## Re: Prove using induction on n that 3 divides (4^n)+5

First of all , i didn't give my solution until the others solved it by induction ! You know what , solving problems with different ways is the best way to be good at maths , this is what my brother (who is by the way a winner of a silver medal in the IMO) used to tell me . Take it or leave it .
Anyway , thanks for being nice and sorry if i was wrong by giving another (better ? ) solution for the exercise .

10. ## Re: Prove using induction on n that 3 divides (4^n)+5

$4 \equiv 1[3]$

As "4 is defined as 1 * 3", but that doesn't make sense to me.

11. ## Re: Prove using induction on n that 3 divides (4^n)+5

I don't see the point of giving non-induction answers to questions that clearly state
to answer using Proof By Induction.
I think there is nothing wrong feeling generous and giving another way to solve it after the problem had been solved through the required method. I myself have benefited and learned from posts of people doing so in more than one occasion (which isn't surprising, as one of the prime qualities of MHF is that is isn't 'give as dictated' answer service, so to speak). Apologies for the off-topic, of course.

12. ## Re: Prove using induction on n that 3 divides (4^n)+5

Originally Posted by TimM

$4 \equiv 1[3]$

As "4 is defined as 1 * 3", but that doesn't make sense to me.
Modular arithmetic - Wikipedia, the free encyclopedia

13. ## Re: Prove using induction on n that 3 divides (4^n)+5

Originally Posted by TimM

$4 \equiv 1[3]$

As "4 is defined as 1 * 3", but that doesn't make sense to me.
what that notation means is "4 is congruent to 1 modulo 3".

in other words, the difference between 4 and 1 is a multiple of 3 (they are a multiple of 3 "apart").

the usefulness of this derives from the fact that if a = r (mod n) and b = s (mod n), then

a+b = r+s (mod n), and ab = rs (mod n). by convention, r and s are integers between 0 and n-1 (inclusive).

for example, we have that 4 = 1 (mod 3), and 8 = 2 (mod 3) (8 - 2 = 6, which is a multiple of 3).

if what i said above is true, than we would expect 12 = 4+8 to be congruent to 1+2 = 3 (mod 3) (which it is, since 12 - 3 = 9

is a multiple of 3), and 32 = (4)(8) to be congruent to (1)(2) = 2 (mod 3) (again true, since 32 - 2 = 30 is a multiple of 3).

congruence is transitive (you can "pass it along", like equality), so since 3 is congruent to 0 (mod 3), 12 is likewise congruent to 0 (mod 3).

in other words, the "remainders" upon division by n of integers, obey many of the same rules as integers do.

this is helpful when considering divisibility questions, since it reduces greatly the number of possible cases to check

(with division by 3, we have 3 possible "remainders" 0,1 or 2). technically, we get what is called a quotient ring,

but the abstract general construction is not necessary to understand this specific case.

personally, the proof i would give is this:

given that 4^k + 5 = 3q,

4^(k+1) + 5 = 4(4^k) + 5 = (3+1)(4^k) + 5

= 3(4^k) + 4^k + 5 = 3(4^k) + 3q = 3(4^k + q).

14. ## Re: Prove using induction on n that 3 divides (4^n)+5

Originally Posted by TheCoffeeMachine
I think there is nothing wrong feeling generous and giving another way to solve it after the problem had been solved through the required method. I myself have benefited and learned from posts of people doing so in more than one occasion (which isn't surprising, as one of the prime qualities of MHF is that is isn't 'give as dictated' answer service, so to speak). Apologies for the off-topic, of course.
It is recommended MHF policy to stay on topic.
When a question states to specifically answer in a certain way,
why not concentrate on the requested method?
The objective is to master "Proof By Induction".

You're missing my point entirely.

The given series is a simple arithmetic series,
however I personally would not encourage a student to answer the question as worded
using any other method.
In an exam, it is of no use to offer an alternative.
It is good of course to learn other ways,
but at least if offering an alternative,
one should let the student know not to offer the alternative in an assessment.