Is there any easy way to do this? I get the basic step.. where you prove it for some number.. but I don't get the induction step.
Do you literally take the given equation that you just proved with the basic step.. and plug in (k+1)?
I really don't understand how to prove by induction other than the general explanation where you show that if it works for some number, than it will also work for some number + 1 based on assumptions.
Thanks
On
The principle of Induction says that $\forall P[[P(0) \wedge \forall k\in \mathbb{N}(P(k)\Rightarrow P(k+1)]\Rightarrow \forall b\in \mathbb{N} [P(n)]]$...thus if $P$ is any predictate and you prove $P$ for $n=0$ $and$ then assuming that it is true for $n=k$ you prove $P$ for $n=k+1$ then $P$ is true forall $n\in \mathbb{N}$. So, in general when you assume $P(n)$, then you put the value of $n$ in $P$ and for $n+1$ you replace it by $n+1$ and after some manipulation you need to decompose it in $P(n)$ and some other terms so that you can use your induction hypothesis. Most of the time this thing works, but every problem has different strategy.
First we show that it holds for the "base case", usually $n=1$ or $n=0$ but that can vary.
Then we assume it holds for $n=k$ and then prove that provided it holds for $n=k$ it will also hold for $k+1$. In other words, if the formula is valid for an integer, it will always be valid for the next integer.
Combining this with our original demonstration that it is true for $n=1$, it means it will be true for $n=2$. But if it is true for $n=2$ it should be true for the next integer, i.e, $n=3$. This is kind of like a "domino effect" that ad infinitum.