0

I'm currently analyzing whether functions with the form $f(n) = a * b ^ {g(n)} + c * d ^ {h(n)}$ yield a result that is divisible by a number e for all $n \in \mathbb{N}$.

Often I can show that this is true via induction. However, I've found some examples, e.g. $a, c = 1, b=13, d=14, g(n) = n+1, h(n) = 2n-1, e=183$ where the above statement seems to be true but I cannot prove this using induction.

So I'm wondering which methods I could use here (instead of induction) in order to prove or disprove such a statement in general.

Mefitico
  • 1,845
quant
  • 105

1 Answers1

2

$183=13^2+13+1=14^2-14+1={13^3-1\over12}={14^3+1\over15}$ so $13^3\equiv1\bmod{183}$ and $14^3\equiv-1\bmod{183}$.

So the powers of $13$, reduced modulo $183$, go $1,13,-14,1,13,-14,\dots$

and the powers of $14$ go $1,14,13,-1,-14,-13,1,14,13,-1,-14,-13,\dots$.

The odd powers of $14$ then go $14,-1,-13,14,-1,-13,\dots$.

Now if you match up $13^{n+1}$ with $14^{2n-1}$ then you see they cancel.

To put it another way, $14^{2n-1}=(14^2)^n14^{-1}\equiv(13)^n(-13)=-(13)^{n+1}\bmod{183}$.

Now I know you want general methods, not just this particular case, but

1) there are no general methods, and

2) this case highlights one approach that may work from time to time, namely, sometimes $b$ and $d$ may have short periods modulo $e$, and they might line up in such a way as to cancel. In particular, if $e$ is of the form $r^2+r+1$ for some $r$, then something like this should happen for $b=r$, $d=r+1$.

Gerry Myerson
  • 179,216
  • By the way, you could handle this particular example by induction, but you have to prove that if it's true for $n$, then it's true for $n+3$ (and you need base cases $n=1$, $n=2$, and $n=3$). – Gerry Myerson Nov 11 '19 at 22:08