Если при доказательстве утверждения с помощью математической индукции вместо 1 взять другой базиc, придется доказать и для n+1, и для n-1?

Не обязательно.

Надо смотреть на то -- какие свойства вас интересуют. Тут возможны варианты:

1. вас интересуют свойства только для "неограниченно больших" чисел (условно поведение на бесконечности -- типичная задача, скажем из мат.анализа) -- тогда доказываете для произвольной базы P(n) и шаг индукции $P(n) => P(n + 1)$

2. Вас интересует утверждение P(n) для всего множества целых чисел  -- тогда доказываете для любой базы индукции P(n) и оба шага индукции: $P(n) => P(n + 1)$ $P(n) => P(n - 1)$.

3. Вас интересует поведение на всём множестве N, но шаг индукции доказывается только при большом n (вероятно это ваш случай):
$ (∀n > X, P(n)) => P(n + 1)$. Тут можно просто доказать все утверждения для небольших n (меньших X). А для n >= X -- уже доказать индукцию.
Насколько я помню довольно много "популярных" математических утверждений имеют именно такую структуру. Когда все случаи для малых n просто рассматривают отдельно.