Historically first uses of mathematical induction 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.
 A: Induction
http://jeff560.tripod.com/i.html
Mathematical Induction
http://jeff560.tripod.com/m.html
A: This is not an answer to your question because you ask for explicit mentioning. However I think this is still relevant to the discussion: some claim Levi ben Gershon (early 14th century) used induction in some sense. I read this in John Stillwell's "Mathematics and its history", p193:

"Levi ben Gershon comes very close to using mathematical induction, if not actually inventing it .... Rabinovitch (1970) offered an exposition of some of Levi ben Gershon's proofs that certainly seems to show a division into a base step and induction step, but the induction step needs some notational help to become a proof for truly arbitrary n."

Rabinovitch (1970) above is "Rabinovitch, N.L. (1970). Rabbi Levi ben Gershon and the origins of mathematical induction. Arch. Hist. Exact Sci., 6, 237-248"
A: EDIT: I should have read the other posted answer before writing the answer below.  Obviously, my suggestion
that the name "induction" was coined by Poincare is wrong.  I am curious, then, as to when the name "induction" gained popular currency.  Was Poincare simply taking an established term and turning it to his own purposes in the philosophy of mathematics?

In one of his essays (I forget which one, and don't have the reference at hand) Poincare
discusses mathematical induction in the formal way that we think of it, and explains that
it is this principle that allows mathematical argument to escape the rigid confines of formal tautologies and take flight on mathematical intuition.    In fact, he uses the name induction in deliberate analogy with inductive reasoning in science (to be contrasted with the deductive reasoning that underlies logical manipulations of definitions).   
I don't know how much of his contribution to the formalization of induction is original,
and how much he is building on earlier work.  The wikipedia article on induction has a small
amount of history and mentions Boole, Peano, and Dedekind (all working in the 19th century) and does not mention Poincare, while the wikipedia article mentions Grassmann as well.
This suggests that Poincare is indeed building on their
earlier formulations.    (Aside: I didn't see in either article a statement as to where the precise statement induction originated (in a footnote quoting from Boole in the induction article, the term
induction does not seem to be used), so it seems conceivable that the actual name "mathematical induction" comes from Poincare.)
The wikipedia article on induction mentions Bernoulli as an earlier employer of the "inductive hypothesis". 
It also mentions the well-known "infinite descent" arguments of Fermat,
which are a variation on induction (in fact, they are a direct appeal to the well-ordering of the natural numbers), and mentions several earlier examples, going back to ancient times.  None of these earlier examples are explicitly applying induction in our modern sense, though; rather, they are making arguments or calculation which are implicitly of an
inductive nature.
Summary: I hope that someone who knows more history and has more sources than wikipedia at hand will give a more definitive answer, but my guess is that, while inductive style arguments date back to the beginning of mathematics, the precise logical formulation of inductive arguments dates back to the 19th century (and represents part of the concern for logical foundations that developed in that century), and that the actual name "induction" may originate with
Poincare (in the early 20th century).
A: There are several questions here, so my answer overlaps with some of the
others.


*

*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.

*First published use of induction in some form. Euclid's infinite descent
proof that every natural number has a prime divisor, in the Elements.

*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.

*First mention of "induction". The one suggested by Gerald Edgar is
the earliest I know of.

*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.
