Explaining Proofs by Induction 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!!
 A: 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$.
A: 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!!
A: 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)...
