Suppose we want to prove that a property $P$ is true for every integer in $ℕ_{odd}$ = $\{1,3,5,7,9,...\}$.

Question

Suppose we want to prove that a property $P$ is true for every integer in $ℕ_{odd}$ = $\{1,3,5,7,9,...\}$. Consider the following induction mechanism:

1. Base case: Verify the property $P(1)$

2. Inductive step: Prove that for all $k ≥ 1, P(k) ⇒ P(k + 1)$

(a) Why might the above mechanism not constitute a valid proof?

(b) How would you modify the inductive step to obtain a valid proof?

(c) Use your modified mechanism to prove that every integer $n$ ∈ $ ℕ_{odd}$ satisfies $2^n+3^n = 5m$, where $m$ is an integer.

What I did

A) What I thought is that it doesn't constitute a valid proof because it is not complete. In that it should have been a strong induction for the set of all odd numbers in the set $ℕ_{odd}$. It only verifies $P(1)$.

B) I am not sure, but to continue on from the previous one, maybe continue by changing the inductive step to constitute for all odd numbers in the set $ℕ_{odd}$.

C) I am also not sure, but most likely this is an inductive proof where base case = $2^1+3^1 = 5(1) = 5$. Inductive step, assuming $k$ is in the set of all odd integers. $P(K)$ = $2^k+3^k= 5m $ and prove this for $k+1$. $P(K+1)$ = $2^{2k+1}+3^{2k+1} = (2^k)^2 \times 2 + (3^k)^2 \times 3 = 5m$, which leads to $P(K)$.

Question

I need help with B) and C) for how to modify the inductive step to obtain a valid proof, and use that modified mechanism to satisfy the proof.

Answer 1

Note that, in the example where $P(k)$ means $2^k+3^k=5m$ for some integer $m$,

$P(1)$ is true, but $P(2)$ is not true, so you can't prove that $P(n)\implies P(n+1)$.

To prove $P(n)$ for all odd $n$, you can show that $P(n)\implies P(n+2)$

using $2^{n+2}+3^{n+2}=4(2^n)+9(3^n)=4(2^n+3^n)+5(3^{n})$.

Answer 2

$$\varphi:\mathbb N\to \mathbb N_{odd},k\mapsto 2k+1$$ is a bijection, whose reciprocal bijection is$$\varphi^{-1}:\mathbb N_{odd}\to \mathbb N, n\mapsto \frac{n-1}{2}$$ To prove that an assertion $P(n)$ is TRUE for all $n\in \mathbb N_{odd}$ is then to prove that $$\forall k \in \mathbb N, P'(k):=P(\varphi(k)) \text{ is TRUE}$$What can be done by classical induction. $$P'(k)\to P'(k+1)$$is written then $$P(2k+1)\to P(2(k+1)+1)=P(2k+1\color{green}{+2})$$ie $$P(n)\to P(n\color{green}{+2})$$as @J.W.Tanner simply and nicely explained to you.

Answer 3

(A) I don't fully understand what you have written, but from what I got, your answer is wrong. The mechanism might not be valid because the property may not hold for some even number. If the property holds for all natural numbers, then the mechanism works and proves that the property is true for all odd numbers. If not, say the property first fails at some even number $k$, then the method will only show the property for numbers $1$ to $k-1$. An example is the problem in (C). Since $P(2)$ is not true, you cannot show $P(k)\implies P(k+1)$.

(B) Again, not sure about your wording, but the idea is to not bother about even numbers. Check $P(1)$ and then verify that $P(k)\implies P(k+2)$ for all odd $k$. Even if $P(k)\implies P(k+2)$ is false for some even $k$, it will not matter. An alternate way to do this is, let $n=2m-1$ and then use usual induction on $m$: check $m=1$ and then that the property holding for $m$ implies that the property holds for $m+1$ as well.

(C) Try doing $P(k)\implies P(k+2)$, or the $n=2m+1$ trick.

Hope this helps. :)