When proving the result using mathematical induction basis step (which often involves verifying proposition for n = 0 or 1) is usually trivial. But inductive step illustrating that if proposition is true for n = k, then it is true for n = k+1 -- is frequently much more complicated.
Are there any examples of the inductive proof where inductive step is trivial but basis step is complicated and/or difficult?