Discrete math induction proof (divisibilty)

Question

How to show that $10^n -(-1)^n$ is always divisible by $11$ through proof of induction?

Answer 1

With $a_n=10^n-(-1)^n$, note that $a_{n+2}=100 a_n+99\cdot(-1)^n$, so you might find it easier to perform induction for $n$ odd and even separately

Answer 2

Note that we have $$ 10^n - (-1)^n = 10\cdot (10^{n-1} - (-1)^{n-1}) \pm 11 $$ where the $\pm$ depends on the parity of $n$.

Answer 3

HINT: The induction step is a little tricky; it might help to take a look at some numbers first in order to get a better idea of just what’s going on. The first few values, for $n=1,2,3,4,5$, are $11,99,1001,9999$, and $100001$; dividing these by $11$ yields $1,9,91,909,9091$. Each of these numbers is roughly $10$ times the previous one. In fact, a very nice pattern is apparent:

$$\begin{align*} 9&=10\cdot1-1\\ 91&=10\cdot9+1\\ 909&=10\cdot91-1\\ 9091&=10\cdot909+1\;. \end{align*}$$

This suggests that if we let $a_n=10^n-(-1)^n$, and if $a_n$ really is a multiple of $11$ for all $n$, say $a_n=11b_n$, so that $b_1=1$, $b_2=9$, $b_3=91$, and so on, then

$$b_{n+1}=10b_n+(-1)^n\;.$$

This would mean that

$$\begin{align*} a_{n+1}&=11b_{n+1}\\ &=11\left(10b_n+(-1)^n\right)\\ &=110b_n+11(-1)^n\\ &=10a_n+11(-1)^n\;. \end{align*}$$

Conversely, if we could show that $a_{n+1}$ really is always $10a_n+11(-1)^n$, the induction step in proving that $a_n$ is a multiple of $11$ for each $n$ would be easy: by the induction hypothesis $a_n$ is a multiple of $11$, and $11(-1)^n$ is certainly a multiple of $11$, so their sum is a multiple of $11$. So can we prove that $a_{n+1}=10a_n+11(-1)^n$, i.e., that

$$10^{n+1}-(-1)^{n+1}=10\left(10^n-(-1)^n\right)+11(-1)^n\;?$$

Answer 4

As others have pointed out, induction isn't necessary.

$10^n - (-1)^n = (11) \sum_\limits{i=0}^{n-1} 10^i$

But, if this is an exercise in writing proofs by induction.

base case: $n = 1\\ 10^1 - (-1)^1 = 11$

Inductive hypothesis: Assume that $10^n-(-1)^n$ is divisible by 11.

show that: $10^{n+1}-(-1)^{n+1}$ is divisible by 11.

$10(10^n)+(-1)^n\\ 10(10^n)-10(-1)^n + 11(-1)^n\\ 10(10^n-(-1)^n) + 11(-1)^n$

11 divides the fist term from the inductive hypothesis, and clearly 11 divides the 2nd term.

Answer 5

An obvious generalization:

If $b \in \mathbb{N}$ and $b \ge 2$ then $(b-k)^n-(-k)^n$ is always divisible by $b$ for $n, k \in \mathbb{N}$.

Proof (one of many): Since $u^n-v^n =(u-v)\sum_{j=0}^{n-1} u^j v^{n-1-j} $, $(b-k)^n-(-k)^n =((b-k)-(-k))\sum_{j=0}^{n-1} (b-k)^j (-k)^{n-1-j} =(b)\sum_{j=0}^{n-1} (b-k)^j (-k)^{n-1-j} $, and this is always divisible by $b$.

Answer 6

The case $n=0$ is obvious. Suppose $10^n-(-1)^n=11k$. Then $$ 10^{n+1}-(-1)^{n+1}=10(11k+(-1)^n)+(-1)^n =11\cdot 10k+11\cdot(-1)^n $$