1

We consider the statements $P (n)$: "$4^n −1$ is divisible by $3$" and $Q(n)$: "$4^n + 1$ is divisible by $3$" where $n \in \mathbb{N}$.

(1) Show that both inductive steps $P (n) \implies P (n + 1)$ and $Q(n) \implies Q(n + 1)$ are true for all $n \in \mathbb{N}$.

(2) For which values of $n \in \mathbb{N}$ is $P (n)$ true ? Justify!

(3) Show that $Q(n)$ is actually false for all $n \in \mathbb{N}$.

For the previous question, I am able to show that both inductive steps are true for both $P(n)$ and $Q(n)$; however, I am not too sure how to answer following parts of the question. For part 2, I am completely lost. For part 3, I believe it is because the base case $n = 1$ is false. Any extra help would be appreciated. Thank you!!

José Carlos Santos
  • 427,504
Michelle Drolet
  • 629
  • 5
  • 14

3 Answers3

1

For $(2)$, verify that $P(1)$ is true, hence $P(n)$ is true for all $n \in \Bbb N$ by induction.

For $(3)$, since $4^n-1$ is divisible by $3$, $4^n+1 = (4^n-1)+2$ is not divisible by $3$ (and leaves a remainder of $2$) for all $n$.

Kenny Lau
  • 25,049
1

First of all let's check if they are true for $1$ or $0$ for that matter, I don't how you prefer $\mathbb{N}$. I'll do it for $1$;

$$Q(1)=4^1+1=5$$ which is not divisible to $3$ for $1$ which means it isn't valid for all $\mathbb{N}$. Going on;

$$P(1)=4^n-1=3$$ which is divisible by $3$ it looks good right now, now I will try to show that this is correct for $n+1$ if it's correct for $n$;

$$P(n+1)=4^{n+1}-1=(4-1)(4^n+4^{n-1}+\cdots+1)$$ is divisible by $3$ therefore it is true for

1)The beginning $1$

2)It is true for $n$ so it must be true for $n+1$ and it is!!

Done!!

Deniz Tuna Yalçın
  • 1,230
0

Hint

If P(n) is true then P(n+1) is true too

It's easy to show that $P (1) \implies P (2)$

$S(n)=4^{(n+1)}-1$

$S(n)=4^n*4-1$

$S(n)= (4^n -1 +1 )*4 - 1$

By induction hypothesis $4^n-1 =3k$

$S(n)=(3K+1)*4-1$

$S(n)=12K+4-1$

$S(n)=3*(4K+1)$

So $$P (n) \implies P (n + 1)$$ is true...

The same apply for Q(n+1)...

user577215664
  • 40,625