# Induction: How to prove propositions with universal quantifiers?

In my book, they prove with mathematical induction propositions with successions like this:

$$1 + 3 + 5 + \cdots + (2n-1) = n^2$$

In all exercises. However, recently I took some exercises from a different paper and instead of these it told me to prove this:

$$\forall n \in N (11 / (10^{2n+1} + 1 ))$$

Or perhaps this:

$$\forall n \in N (n < 2^n)$$

(I can't find how to write the natural numbers set symbol. $N$ is it there.)

And now I'm lost. This is is what I did with the first one:

Prove that the proposition works for $n=1$

$$11 / (10^3+1) \implies 11/1001 \implies \exists x \in N(11x=1001)$$ Which is true, if you take $x = 91$.

Assume $$\forall n \in N (11 / (10^{2n+1} + 1 ))$$ We have to prove: $$\forall n \in N (11 / (10^{2n+3} + 1 ))$$ We prove it:

Which I don't know how to do. Curiously enough, my book only shows exercises with successions, so I guess that this exercise can be, somehow, written as a succession? I am not sure about that. Any ideas?

-
You can get $\mathbb N$ using \mathbb N and $\mid$ using \mid. – joriki Nov 24 '12 at 21:49

I'm not sure what you mean by "writing a proof as a succession". I can do it as follows:

$$10^{2n+3}+1=100\cdot 10^{2n+1}+1=99\cdot 10^{2n+1}+\left(10^{2n+1}+1\right)$$

Look at the rightmost expressions: obviously, the first summand is a multiple of $\,11\,$ since $\,99\,$ is, and the second one is also a multiple of $\,11\,$ by the inductive hypothesis. Since the sum of two multiples is again a multiple we're done.

-

You are misunderstanding induction here.

The $\forall$ is always part of it. For example, the real statement for your first result is $$\forall n\in\mathbb N: 1+3+...+(2n-1)=n^2$$

In general, if your equation is: $$\forall n\in\mathbb N: P(n)$$, the principal of mathematical induction says it is enough to show:

$$P(1)$$ and $$\forall n\in\mathbb N: P(n)\implies P(n+1)$$

So to prove that $11\mid 10^{2n+1}+1$, you first show $11\mid 10^{3}+1$ and then prove that if $11|10^{2n+1}+1$ then $11|10^{2n+3}+1$.

-