Linear recurrence fits with factorial finitely often

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Linear recurrence fits with factorial finitely often

G H J

Reveal topic tags

Linear Recurrences

Diophantine equation

L

G H BBookmark kLocked kLocked NReply

Source: Bulgaria Balkan MO TST 2025

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1369 posts

#1 h Apr 9, 2025, 10:25 PM

Y by

Let $k\geq 3$ be an integer. The sequence $(a_n)_{n\geq 1}$ is defined via $a_1 = 1$ , $a_2 = k$ and
$a_{n+2} = ka_{n+1} + a_n$ for any positive integer $n$ . Prove that there are finitely many pairs $(m, \ell)$ of positive integers such that $a_m = \ell!$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

internationalnick123456

135 posts

internationalnick123456

#2 h Apr 10, 2025, 6:03 AM • 1 Y

Y by MS_asdfgzxcvb

Define $\lambda_1 = \dfrac{k + \sqrt{k^2+4}}{2}$ and $\lambda_2 = \dfrac{k - \sqrt{k^2+4}}{2}$ . Using induction, we have $a_n = \dfrac{\lambda_1^n - \lambda_2^n}{\sqrt{k^2+4}},\forall n\in\mathbb N$ Case 1. $k$ has an odd prime divisor $p$ . Then $p\nmid k^2+4$ . We have $p\nmid a_{2n-1}$ , and $a_{2n} =\dfrac{1}{2^{2n-1}}\sum_{i=1}^{n}k^{2i-1}(k^2+4)^{n-i}\binom{2n}{2i-1}$ We will prove that $v_p\left(k^{2i-1}(k^2 + 4)^{n-i}\binom{2n}{2i-1}\right)>v_p(2kn),\forall 2\leq k\leq n$ .
Indeed, the inequality is equivalent to $(2i-2)v_p(k) + v_p\binom{2n}{2i-1} > v_p(2n)$ Notice that $v_p\binom{2n}{2i-1}\geq v_p(2n) - v_p(2i-1)$ . Hence, it is sufficies to prove that $(2i-2)v_p(k)\geq v_p(2i-1),\forall i\geq 2$ . However, this inequality is quite trivial since $p^{2i-2}\geq 2i-1$ and $v_p(k)\geq 1$ .
Hence, $v_p(a_{2n}) = v_p(kn),\forall n\in\mathbb N$ . Therefore, if $a_m = \ell!$ for some $\ell\geq p$ , we have $v_p(mk)=v_p(\ell!) = \dfrac{\ell - s_p(\ell)}{p-1}\geq \dfrac{\ell - \log_p\ell}{p-1}$ $\Rightarrow \ell = O(\log_p m)$ , whereas $a_m = \Omega(\lambda_1^m)$ . Since $\lim\dfrac{\lambda_1^m}{{\log_pm}^{\log_pm}} = +\infty$ , we conclude that there exists finitely many pairs $(m,\ell)$ satisfying the conditions.
Case 2. $k=2x$ where $x$ is a power of $2$ . Similarly, we have $2\nmid a_{2n-1},\forall n\in\mathbb N$ , and $a_{2n} = \sum_{i=1}^nx^{2i-1}(x^2+1)^{n-i}\binom{2n}{2i-1}$ Since $x$ is even, similar to Case 1 we get $v_2(a_{2n}) = v_2(2xn)$ . Thus, by the same method, we can show that there exists finitely many pairs $(m,\ell)$ that satisfies $a_m = \ell!$ . (qed)

This post has been edited 1 time. Last edited by internationalnick123456, Apr 10, 2025, 6:05 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1369 posts

#3 h Apr 10, 2025, 8:12 AM

Y by

Main idea: Write $a_n$ in explicit form, expanded with binomial coefficients summation and work with $\nu_p$ where $p$ is an odd prime divisor of $k^2+4$ . (Note that $k^2+4$ is not a power of $2$ for $k\geq 3$ by mod $8$ .]

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a