I'm interested in find out what were some of the first uses of mathematical induction in the literature. 


I am aware that in order to define addition and multiplication axiomatically, mathematical induction in required. However, I am certain that the ancients did their arithmetic happily without a tad of concern about induction.


When did induction get mentioned explicitly in the mathematical literature? Definitely this places before about 1800 when the early logicians started formulating axioms for arithmetic.



Historically first uses of mathematical induction
There are several questions here, so my answer overlaps with some of the
others.


1. First use of induction in some form. I would nominate the "infinite
descent" proof that $\sqrt{2}$ is irrational -- suppose that $\sqrt{2}=m/n$, 
then show that $\sqrt{2}=m'/n'$ for smaller numbers $m',n'$
-- which probably goes back to around 500 BC.
2. First published use of induction in some form. Euclid's infinite descent
proof that every natural number has a prime divisor, in the *Elements*.
3. First use of induction in the "base step, induction step" form. I
suggest Levi ben Gershon and (more definitely) Pascal, as mentioned in
danseetea's answer.
4. First *mention* of "induction". The one suggested by Gerald Edgar is
the earliest I know of.
5. First realization that induction is fundamental to arithmetic:
Grassmann's *Lehrbuch der Arithmetik* of 1861, where he defines addition
and multiplication by induction, and proves their ring properties by 
induction. This idea was rediscovered, and built into an axiom system by 
Dedekind, in his *Was sind und was sollen die Zahlen?* of 1888. It
became better known as the Peano axiom system, when Peano redeveloped
it a couple of years later.


