Is it valid to perform an induction proof using $2 k$ as opposed to using $k + 1$ in your inductive step? I tried searching but all I saw is that induction is done using $k + 1$.
Asked
Active
Viewed 334 times
0
-
It depends upon the theorem in question. If the theorem relates to properties of numbers of the form $k_i^2$, for $i = 1, \ldots$, then induction on $2 k$ can be valid. – David G. Stork May 12 '18 at 00:00
2 Answers
2
Induction is done with $(k+1)$ so that the proposition can be proved for all integers.
If you prove a base case $n$ and prove the inductive step using $(n+1)$ then you have proved the proposition for $n,\,n+1,\,n+2\,...$ i.e. all integers greater than or equal to $n$.
If you use $2n$ then you have instead proved that the proposition is true for $n,\,2n,\,4n,\,8n,\,16n\,...$ which is valid, but generally not as useful.
PKBeam
- 432
1
It depends on what you want to prove. You could use the induction step $2k \rightarrow$ $2k+2$ to prove something for even numbers $n\in \mathbb Z$
You might as well make it arbitrary and choose a different step. $k \rightarrow k+m$ to prove something for integers of the form $n_o+t*m$ where $n_o$ is the base case
An example of "odd-steps" would be Cauchy-Induction which is also called "forward/backward-induction"
XPenguen
- 2,301