"Cascade induction"?

I refer to this answer.

The answer is based on several simplification steps, all of them proven by induction.

• $S_n = 2903^n - 803^n - 464^n + 261^n$
• $T_n = 2642\cdot2903^n - 542\cdot803^n - 203\cdot464^n$
• $U_n = 6443838\cdot2903^n - 183738\cdot803^n$

are all proven to be divisible by 1897.

• First statement is the original statement from the question.
• Second statement is the induction step for the first statement.
• Third statement is the induction step for the second statement.

Is there a name for the method applied there? "Cascade induction", let's say?

Solution 1:

What's being cascaded is not induction but, rather, telescopy (to essentially construct the difference operator / recurrence that annihilates $\,f_n = S_n).\ $ The telescopic step is this.

Theorem $\ \ m\mid f_n= a^n\! + g_n\,$ for all $\,n\iff m\mid g_{n+1}\!-ag_n\,$ for all $\,n,\,$ and $\,m\mid f_0$

Proof $\ (\Rightarrow)\ \ f_{n+1}\!-af_n = g_{n+1}\!-ag_m\,$ so $\,m\mid f_{n+1},f_n\Rightarrow\, m\mid $ LHS $\,\Rightarrow m\mid $ RHS.

$\ (\Leftarrow)\ $ Induction Base: $\,m\mid f_0\,$ by hypothesis. Step: $\,m\mid f_n,\,$ RHS $\,\Rightarrow\, m\mid $ RHS $+ a f_n = f_{n+1}$

Remark $\ $ Let $S\,$ be the $\,n$-shift $\,S f_n = f_{n+1}.\,$ Then $\,(S\!-\!a) a^n = a^{n+1}\!-a a^n = 0.\,$ Therefore $\, (S-a)(S-b)(S-c)(S-d)\,$ kills $\,f_n = a^n + b^n + c^n + d^n.\,$ This yields an order $4$ constant coeff recurrence for $\,f_n,\,$ say $\,f_{n+4} = c_3 f_{n+3} + c_2 f_{n+2} + c_1 f_{n+1} + c_0 f_n.\,$ Hence by (strong) induction we deduce that $\,m\mid f_n\,$ iff $\,m\mid f_0,f_1,f_2,f_3,\,$ so $\,\gcd(f_0,f_1,\ldots) = \gcd(f_0,f_1,f_2,f_3).\,$ The linked proof amounts to constructing this recurrence in $4$ steps, using the above Theorem for each step, which amounts to applying $\,S\!-\!a\,$ to kill $\,a^n,\,$ then applying $\,S\!-\!b\,$ to kill $\,b^n,\,\ldots$

Thus the linked proof can be greatly simplified once one observes that the form of $\,f_n\,$ implies that it satisfies an order $4$ recurrence, so we need only check the first $4$ values. But we can simplify the proof even further. As I mention in my answer there, by symmetry, it suffices to check that $\{2903,\, 261\}\ \equiv\ \{803,\, 464\}\,\ {\rm mod}\,\ 271,7.\,$ Then the induction is encapsulated in the well-known Congruence Power Rule $\, A\equiv a\,\Rightarrow\, A^n\equiv a^n.\,$ This is a prototypical example of how exploiting innate symmetry leads to great simplification.