Induction Proof without Explictly Using The Induction Hypothesis?
I have encountered several problems where one can prove the desired result without actually needing the induction hypothesis. More specifically, you basically just pick $n \in \mathbb{N}$ and run through the argument. In fact, the solution manual does exactly this (without breaking the problem in steps). What caused me some concern is that I encountered a problem where I can prove the desired result just picking arbitrary $n$, but I can prove it in a manner when I explicitly use the induction hypothesis. What does it mean when you don't actually need the induction hypothesis? Please help!
Here's the problem: Prove that for $p_{k} \geq 0$ and $\sum^{n}_{k=1} p_{k} = 1$, if $g(x) = \sum^{n}_{k=1} p_{k} \cos(\beta_{k}x)$, then $g^{2}(x) \leq \frac{1}{2} (1+ g(2x))$. We use the fact that if $f(x)= \cos(\beta x)$, then $f^{2}(x)= \frac{1}{2}(1+f(2x))$.
$\endgroup$ 12 Answers
$\begingroup$When you don't need to use the induction hypothesis, it means that you don't need to use induction. You can just do a direct proof.
$\endgroup$ 1 $\begingroup$I guess “Proving (by induction) of a hypothesis by just considering an arbitrary n (only)” or “cross(ing) out the entire beginning of the proof” means “without testing the truth of the hypotheses when n = 1”.
This is fatal!
Let me demonstrate this by a counter-example:
Suppose that we have the following hypothesis:-
$H(n): \sum_{i=1}^n i^3 = [\frac {1}{2} n(n+1)]^2 + L$ ; where L is any arbitrary number.
Of course, this is not difficult to see that
If $H(k)$ is true, then
$H(k+1) = \sum_{i=1}^k i^3 + (k+1)^3$
$= [\frac {1}{2} k(k+1)]^2 + (k+1)^3 + L$
$= … = [\frac {1}{2} (k+1)(k+2)]^2 + L$; meaning $H(k+1)$ is also true.
However, obviously, $H(n)$ is definitely a false statement.
The key-point lies in the fact that the testing of $H(0)$ has been skipped.
$\endgroup$
