Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
Assuming your algebra is right, yes. –  T. Bongers Jan 10 at 23:20
1  
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 at 1:49
1  
@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 at 4:11

2 Answers 2

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

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

share|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|improve this answer

Your Answer

 
discard

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.