First, teach recursion. The implementation is more concrete, and a program that computes case n + 1 from case n is essentially going through an inductive argument. read more
If they still don't agree, we may possibly need to go deeper, by showing them how are natural numbers constructed (successor sets etc.) and the well-ordering principle in natural numbers (which is equivalent to mathematical induction in some way), but I don't think we need to go that way. read more
The best way to make your students accept mathematical induction is to make them "suffer" through the pains of calculations. For example, "Show that for each $n$, $\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$." and ask them to calculate by hand. read more