Assume that $ \alpha$ and $ \beta$ are two roots of the equation: $ x^2-x-1=0$. Let $ a_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$, $ n=1, 2, \cdots$. (1) Prove that for any positive integer $ n$, we have $ a_{n+2}=a_{n+1}+a_n$. (2) Find all positive integers $ a$ and $ b$, $ a<b$, satisfying $ b \mid a_n-2na^n$ for any positive integer $ n$.
Problem
Source: CWMO 2002 P7
Tags: induction, number theory proposed, number theory
28.12.2008 22:11
(1) is trivial - induction and $ x^{n+2}=x^nx^2=x^n(x+1)$ -- $ \alpha$ and $ \beta$ satisfy this.
22.01.2012 08:45
(1)Nothing $\alpha+\beta=1$ and $\alpha \beta=-1$ we have $\alpha^{n+2}-\beta^{n+2}=(\alpha+\beta)(\alpha^{n+1}+\beta^{n+1})-\alpha\beta(\alpha^n-\beta^n)=$ $=(\alpha^{n+1}-\beta^{n+1})+(\alpha^n-\beta^n)$ Dividing two sides $\alpha-\beta$ we have $a_{n+2}=a_{n+1}+a_n$
22.01.2012 09:03
(2)By assumption we have $b|a_1-2a$ that is $b|1-2a$. But $b>a$ so $b=2a-1$. Moreover for an arbitrary positiva integer $n$ we have $b|a_n-2na^n, b|a_{n+1}-2(n+1)a^{n+1}, b|a_{n+2}-2(n+2)a^{n+2}$ Combining $a_{n+2}=a_{n+1}+a_n$ and $b=2a-1$ an odd number we have $b|(n+2)a^{n+2}-(n+1)a^{n+1}-na^n$ But $gcd(a,b)=1$ so $b|(n+2)a^2-(n+1)a-n$ (1) Taking $n$ as $n+1$ in (1) we have $b|(n+3)a^2-(n+2)a-(n+1)$ (2) Subtracting the right side of (1) from tha same side of (2) we have $b|a^2-a-1 \to 2a-1|a^2-a-1$ But $2a^2\mod a(mod2a-1)$therefore $2a-1|-a-2, 2a-1|-2a-4$ So $2a-1|-5$, $2a-1=1$ or 5 But $2a-1=1$ implies $b=a$ a contraction. So $2a-1=5, a=3, b=5$ We will prove in the following that when $a=3$ and $b=5$ for any positive integer n we have $b|a_n-2na^n$ that is $5|a^n-2n3^n$
22.01.2012 09:20
When $n=1,2$ since $a_1=1 a_2=\alpha+\beta=1$ this problem is easy. Assume that when $n=k, k+1$ this conclusion is true, that is $5|a_k-2k3^k, 5|a_{k+1}-2(k+1)3^{k+1} \to 5|(a_{k+1}+a{k})-2k3^k-2(k+1)3^{k+1} \to$ $5|a_{k+2}-23^k(4k+3)$ To prove $5|a_{k+2}-2(k+2)3^{k+2}$we need only to prove $5|2(k+2)3^{k+2}-2(4k+3)3^k \to 5|9(k+2)-(4k+3) \to 5|5k+15$Obviously the latter holds.
14.02.2023 21:36
No.(i) Proof of Newton Sum