This is a question in a unit called design and analysis of algorithms, and what exactly is meant by the term prove by induction??

Proof by induction means that if one particular case is true, this is sometimes called the base case, then every other case will be true as well.

Sorry man, I forget how to write proofs.