# Legality of doubly inductive proof requiring two base cases

I aim to show that the proposition $P_n$: "$11^n - 4^n$ is divisible by $7$" is true for all $n\in\mathbb{N}$. Assume that for some $n \ge 2$, $P_n$ is true. Then since \begin{align} 11^{n+1} - 4^{n+1} &= 15\Big(11^{n} - 4^{n}\Big)- 44\Big(11^{n-1}-4^{n-1}\Big) \end{align} $P_{n+1}$ is true if $P_{n-1}$ (in addition to $P_n$) is true.

Can I then conclude that the proposition is true for all $n\in\mathbb{N}$ by induction, as long as I show that it holds for the two base cases $n = 1$ and $n = 2$?

-
Assuming your algebra is right, yes. – user61527 Jan 10 '14 at 23:20
Well, if it's true for $n=1$ and $n=2$, then it must be true for $n=3$, which together with the $n=2$ case makes it true for $n=4$, which together with the $n=3$ case makes it true for $n=5$... looks like it works to me! – MartianInvader Jan 11 '14 at 1:49
@Doubt, your method is called strong induction(en.wikipedia.org/wiki/Mathematical_induction#Complete_induction) and user84413's answer uses the simplest form(en.wikipedia.org/wiki/Mathematical_induction#Description) – lab bhattacharjee Jan 11 '14 at 4:11

It might be simpler to show that the statement is true for $n=1$, and then assume that it is true for some integer $n\ge1$ and use that

$\;\;\;11^{n+1}-4^{n+1}=11(11^n-4^n)+4^n(11-4)$.

[An alternate way to do this is to use that $11\equiv 4 \pmod{7}$, so $11^n \equiv 4^n \pmod{7}$ for any $n\in\mathbb{N}$.]

-

You can do what you have suggested. Here are two other ways to do the problem:

1) What is known sometimes as strong induction. (You assume the result holds for all $k\leq{n}$ and show that the result holds for $n+1$). This would make things simpler.

2) Another way to think about this is to adjusting your $P_{n}$ to say $11^{n}-4^{n}$ and $11^{n-1}-4^{n-1}$ are divisible by $7$. This way your base case is still $n=1$ but it checks both values in one go.

-