Establish equivalence between the principle of Weak Induction and Strong Induction. I am looking for less jargons from predicate logic and more prominence on simple language. Also, please hint me as to what approach should I use in establishing the implication both way. I know that's the way to get around it.

The two directions of implication:

If something can be proven using weak induction, it can be proven using strong induction.

This is trivial, since the strong inductive hypothesis implies the weak inductive hypothesis.

If something can be proven using strong induction, it can be proven using weak induction.

Suppose you're trying to prove $P(n)$ for natural numbers $n$. Let $Q(n)$ be the statement "$P(k)$ holds for all natural numbers $0 \leq k \leq n$, i.e., $Q(n)$ means $P(0)$ and $P(1)$ and ... and $P(n)$. Clearly $Q(n)$ implies $P(n)$. Show that the strong inductive hypothesis on $P(n)$ is equivalent to the weak inductive hypothesis on $Q(n)$, so a weak inductive proof of $Q(n)$ is a sufficient proof of $P(n)$.
