Let $k>1$ be an integer. The sequence $a_1,a_2, \cdots$ is defined as: $a_1=1, a_2=k$ and for all $n>1$ we have: $a_{n+1}-(k+1)a_n+a_{n-1}=0$ Find all positive integers $n$ such that $a_n$ is a power of $k$. Proposed by Amirhossein Pooya
Problem
Source: 2017 Iran TST second exam day2 p6
Tags: algebra, number theory, Iran, Iranian TST
24.04.2017 20:30
Can't we just calculate the general term formula of An?
24.04.2017 20:32
liekkas wrote: Can't we just calculate the general term formula of An? Of course.
25.04.2017 00:06
25.04.2017 00:20
liekkas wrote: Can't we just calculate the general term formula of An?
25.04.2017 05:28
mihajlon wrote: $ \cdots (k+1)^{n-1}<k^n $ $\Leftrightarrow \left (\frac{k+1}{k} \right )^{n-1}<k$ but since $\frac{k+1}{k}>1$ we know that $\left (\frac{k+1}{k} \right )^{n}\overset{n \rightarrow \infty}{\rightarrow}\infty$, so for some $n: \left (\frac{k+1}{k} \right )^{n-1}>k$
25.04.2017 05:40
I think mihajlon's solution has some mistakes
25.04.2017 12:39
mihajlon solution is wrong. We can prove, that if $n>5$ then $a_n>k^{n-1}+(n-2)k^{n-2}$ So, if $n>k^2-k+2$ then $a_n>k^{n-2}(n-2+k)>k^n$ Maybe we need some modular arithmetics here? We can prove, that $k|a_n \to n=2+3i$
07.05.2017 22:31
I think the answer is $n=1,2$. (Not sure) Some unfinished ideas... Assume that there exists $n\geq3$ such that $a_n=k^m$ where $m\geq2$. Firstly, we can use induction to prove that $\{a_n\}$ has another recurrence relation: $a_n^2+k-1=a_{n+1}a_{n-1}$. Therefore, $$a_{n+1}a_{n-1}=a_n^2+k-1=k^{2m}+k-1,$$$$a_{n+1}+a_{n-1}=(k+1)a_n=(k+1)k^m.$$This implies that $a_{n+1}$ and $a_{n-1}$ are the two roots of the quadratic equation $$x^2-(k+1)k^mx+k^{2m}+k-1=0.$$Thus $$(k+1)^2k^{2m}-4(k^{2m}+k-1)=(k-1)^2(k^{2m}+4k^{2m-1}+4k^{2m-2}+...+4)$$must be a perfect square.
08.05.2017 19:11
It is $t^2-4$
08.05.2017 19:11
Your solution has a mistake
09.05.2017 22:35
Let $\alpha = \frac{\sqrt{k+3}+\sqrt{k-1}}{2}$ and $\beta = \frac{\sqrt{k+3}-\sqrt{k-1}}{2}$. Then $a_n = \frac{\alpha^{2n-1} + \beta^{2n-1}}{\alpha + \beta}$. Suppose that for some $n > 2$ and positive integer $m$, $k^m = a_n$. Because $k^{n-1} < a_n$, we have $m \geq n$. Thus $k^n \leq k^m = a_n < (k+1)^{n-1}$, which gives $k+1 < (\frac{k+1}{k})^n$. Crudely, this implies $n \geq k+1$. Next, pick any prime divisor $p$ of $2n-1$ and suppose $q$ is any odd prime divisor of $\frac{\alpha^p + \beta^p}{\alpha + \beta}$. By methods similar to this, we have $q = p = 3$ or $q \geq 2p-1$. Now consider \[ k^m = \frac{\alpha^{2n-1} + \beta^{2n-1}}{\alpha + \beta} = \frac{\alpha^{p} + \beta^{p}}{\alpha + \beta} \cdot \frac{\alpha^{2n-1} + \beta^{2n-1}}{\alpha^p + \beta^p} \]Suppose $q^r \mid \mid \frac{2n-1}{p}$. By an analogue of the LTE lemma, we also have $q^r \mid \mid \frac{\alpha^{2n-1} + \beta^{2n-1}}{\alpha^p + \beta^p}$. Because $q \mid k$, the above equation implies $q^{m-r} \mid \frac{\alpha^{p} + \beta^{p}}{\alpha + \beta}$. In particular, \[ q^{m-r} \leq \frac{\alpha^{p} + \beta^{p}}{\alpha + \beta} <(k+1)^{\frac{p-1}{2}} \]We make the following estimates: $q^{m-r} \geq q^{n-r} \geq \frac{q^n}{(2n-1)/p} > \frac{q^n}{n} \geq \frac{q^{k+1}}{k+1}$, while $(k+1)^{\frac{p-1}{2}} \leq (k+1)^{\frac{q-1}{2}}$. Thus we deduce from the above inequality that $\frac{q^{k+1}}{k+1} < (k+1)^{\frac{q-1}{2}}$, which further implies $q^{k+1} < (k+1)^{\frac{q+1}{2}} < (k+1)^q$. But this is impossible because for $3 \leq q \leq k$, we have $q^{\frac{1}{q}} \geq (k+1)^{\frac{1}{k+1}}$. It remains to rule out the possibility that $\frac{\alpha^{p} + \beta^{p}}{\alpha + \beta}$ is a power of $2$. If $k$ is odd, every term of the sequence is odd. If $k$ is even, then $a_j$ is even if and only if $3 \mid 2j-1$. Hence we only need to consider the case where $p = 3$. That is, we shall assume that $2n-1$ is a power of $3$. Because $n > 2$, this implies $9 \mid 2n-1$ and so $a_5 = \frac{\alpha^{9} + \beta^{9}}{\alpha + \beta} \mid a_n = k^m$. But $a_5 = k(k^3+3k^2-3)$, and it is clear that $k^3+ 3k^2 - 3$ cannot divide $k^m$.
23.03.2018 19:09
A nice solution for this problem!!!
Attachments:
New Doc 2018-03-23.pdf (222kb)