Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
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( and user84413's answer uses the simplest form( – lab bhattacharjee Jan 11 '14 at 4:11
up vote 1 down vote accepted

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


[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}$.]

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.