Induction: How to prove that $ab^n+cn+d$ is divisible by $m$.

Question

If $a+d$, $(b-1)c$, $ab-a+c$ are divisible by $m$, prove that $ab^n+cn+d$ is also divisible by $m$.

I want to prove this by induction. For proving $ab^{k+1}+c(k+1)+d$ is divisible by $m$, i want to prove that $ab^k(b-1)+c$ is divisible by $m$ and then add it to $ab^{k}+ck+d$. Any idea how to prove $ab^k(b-1)+c$ is divisible by $m$? Or is there a better way to solve the problem?

Thanks in advance.

Answer 1

We need to proceed by

• base case: $n=0 \implies ab^0+c0+d=a+d$
• induction step: assume $m|ab^n+cn+d$ then

$$ab^{n+1}+c(n+1)+d=ab^{n+1}+bcn+bd-bcn-bd+c(n+1)+d=$$

$$=b(ab^{n}+cn+b)-(b-1)cn-bd+c+d$$

then note

• $m|a+d \implies m|ab+bd \implies m|bd+a-c\implies m|bd-c-d$

Answer 2

Without induction. Let's do some tagging 1st $$m \mid a+d \tag{1}$$ $$m \mid (b-1)c \tag{2}$$ $$m \mid ab-a+c \tag{3}$$ then $$m \mid ab^n+cn+d \iff m \mid a\left(b^n-1\right)+cn+\color{red}{a+d} \overset{(1)}{\iff}\\ m \mid a\left(b^n-1\right)+cn \iff \\ m \mid a(b-1)\left(b^{n-1}+b^{n-2}+...+b^2+b+1\right)+cn \iff \\ m \mid (ab-a+c-c)\left(b^{n-1}+b^{n-2}+...+b^2+b+1\right)+cn \iff \\ m \mid \color{red}{(ab-a+c)\left(b^{n-1}+b^{n-2}+...+b^2+b+1\right)}-c\left(b^{n-1}+b^{n-2}+...+b^2+b+1\right)+cn \overset{(3)}{\iff}\\ m \mid c\left(b^{n-1}+b^{n-2}+...+b^2+b+1\right)-cn \iff \\ m \mid c\left(b^{n-1}-1\right)+c\left(b^{n-2}-1\right)+...+c\left(b^2-1\right)+\color{red}{c\left(b-1\right)} \overset{(2)}{\iff}\\ m \mid c\left(b^{n-1}-1\right)+c\left(b^{n-2}-1\right)+...+c\left(b^2-1\right)$$ which is true because for $\forall k\geq 2$ we have $$c\left(b^k-1\right)=\color{red}{c\left(b-1\right)}\left(b^{k-1}+b^{k-2}+...+b^{2}+b+1\right)$$ and from $(2)$ $$m \mid c\left(b^k-1\right)$$

Answer 3

$\bmod m\!:\ \color{#0a0}{f_{\large n+1}\!-b f_{\large n}} =\, \overbrace{(1\!-\!b)c}^{\large \equiv\ 0}n \,\overbrace{-\color{#c00}d\,b+\color{#c00}d+c}^{\large \equiv\ 0\ \ {\rm by}\ \ \color{#c00}{d}\ \equiv\ -a}\!\equiv\color{#0a0} 0,\ $ so $\ f_n\equiv 0\,\Rightarrow\,\color{#0a0}{f_{n+1}\equiv bf_n\equiv} 0$

Answer 4

As I show here, such results boil down to the first $\,2\,$ terms of the Binomial Theorem, viz.

$\!\bmod m\!:\ c\equiv -a(b\!-\!1)\,$ so $\ \color{#0a0}0\equiv (b\!-\!1)c\equiv -\color{#0a0}{a(b\!-\!1)^2}$ so only $1$st $2$ terms survive below

$\qquad\quad\ \ \ a(1+b\!-\!1)^n =\, \color{#c00}{a\, +\,} n\,\underbrace{a(b\!-\!1)}_{\Large \equiv\ \color{#c00}{-c}}\ +\ \underbrace{\color{#0a0}{a(b\!-\!1)^2}(\cdots)}_{\large \equiv\ \color{#0a0}0}\ \,$ so adding $\ cn+d\ $ we get

$\quad\ \Rightarrow\ \ ab^n +cn+d\, \equiv\, \color{#c00}{a-c\,n}+cn\! +\! d \,\equiv\, a\!+\!d\,\equiv\, 0\ \ \ $ QED

Remark $ $ If you require an inductive proof then do so for the first $2$ terms in the Binomial Theorem. It's easy - the inductive step amounts to multiplying by $\,1\!+\!a\pmod{\!a^2},\,$ viz.

$\!\begin{align}{\rm mod}\,\ \color{#c00}{a^2}\!:\,\ (1+ a)^n\, \ \ \equiv&\,\ \ 1 + na\qquad\qquad\,\ \ {\rm i.e.}\ \ P(n)\\[1pt] \Rightarrow\ \ (1+a)^{\color{}{n+1}}\! \equiv &\ (1+na)(1 + a)\quad\, {\rm by}\ \ 1+a \ \ \rm times\ prior\\ \equiv &\,\ \ 1+ na+a+n\color{#c00}{a^2}\\ \equiv &\,\ \ 1\!+\! (n\!+\!1)a\qquad\ \ \ {\rm i.e.}\ \ P(\color{}{n\!+\!1})\\[2pt] \end{align}$