0

I am a bit confused with this question and any clarification or suggestions would be greatly appreciated.

Suppose that there is a statement involving a positive integer parameter n and you have an argument that shows that whenever the statement is true for a particular n it is also true for n+2. What remains to be done to prove the statement is true for every positive integer? Describe a situation in which this strategy would be applicable.

3 Answers3

4

You just need to show it's true for 1 and 2. The result then follows by induction on n. For example you could prove $n! \ge n$ for every positive integer, using this method, although it's quite a facile example, but just so you get the idea of how induction proofs go, they go like this:

Claim $n! \ge n$ for all odd positive integers.

Proof:

Base case $(n = 1): 1! = 1 \ge 1$

Inductive step: for all n, $n! \ge n$ implies $(n+2)! \ge n+2$

The result follows by induction

Then repeat the exact method for all even positive integers with base case $n = 2$

George Tomlinson
  • 1,346
  • 8
  • 11
1

If you had a theorem which said $X$ is true if $n$ is odd and $Y$ is true if $n$ is even, then you might use this strategy. For example, we might use it in proving:

Theorem: For $n \geq 0$, we have $n^2 \equiv 0 \pmod 4$ if $n$ is even and $n^2 \equiv 1 \pmod 4$ if $n$ is odd.

We prove $X=X(1)$ is true, then show that the truth of $X(n)$ implies the truth of $X(n+2)$. Then repeat separately for $Y(0)$ and $Y(n) \implies Y(n+2)$.

But remember that you also need to prove a base case. There are instances of untrue statements where one can demonstrate the inductive step holds ("if $P(n)$ then $P(n+1)$") without being able to prove a base case.

0

The following is a formalization of the obvious. Denote the statement in question by $P(n)$ and let $$A(m):=P(2m-1),\quad B(m):=P(2m)\qquad(m\geq1)\ .$$ Assume that $A(1)=P(1)$ and $B(1)=P(2)$ are true.

Taking your inductive assumption on $P(\cdot)$ into account we can say the following: When $A(m)=P(2m-1)$ is true then $A(m+1)=P(2m+1)=P\bigl((2m-1)+2\bigr)$ is true. It follows that $A(m)$ is true for all $m\geq1$. Similarly one argues about $B(\cdot)$.

It follows that $P(n)$ is true for all $n=2m-1$ and all $n=2m$, $\>m\geq1$ – in other words: $P(n)$ is true for all $n\geq1$, assuming that $P(1)$ and $P(2)$ are true.