2
$\begingroup$

A sequence of integers $f(n)$ has $f(0) =0$ and satisfies $f(n+2) = a f(n+1)+b f(n)$ for $n \geq 0$, where $a,b \in \mathbb{Z}$. For any positive integer $k$ with $\operatorname{gcd}(k, b)=1$, show that $f(n)$ is divisible by $k$ for infinitely many $n$.

Things I have tried so far: (Please correct me if I made any mistakes below, I am self learning :)

  1. Rewriting the given relation as $$f(n) = \frac{f(n+2) - a f(n+1)}{b}$$

Now for $f(n)$ to be divisible by $k$ it has to be that $f(n+1) - af(n+1) = mk$ for some $m \in \mathbb{Z}.$ which is equivalent to $f(n+2) \equiv a f(n+1) \operatorname{mod} k$ . Now since $f(n)$ is a integer sequence so $f(n+2) \equiv a f(n+1) \operatorname{mod} b$ but unsure how to proceed from here.

Also $k$ does not divide $b$ so my only observations are $pk + qb = \operatorname{gcd}(k,b)$ or that $bx \equiv 1 \operatorname{mod} k$ has a solution for some unknown $x.$

  1. Computing some terms to notice some pattern, however the only term common for the first few is $f(1)$ and no common structures that I can recognise.

I fail to proceed, so any hints or tips would be great help. Thanks!

$\endgroup$
10
  • 1
    $\begingroup$ Do you know how to solve linear recurrences? The recurrence means you can write $f(n)$ as $u\alpha^n+v\beta^n$ where $\alpha,\beta$ are the roots of $x^2-ax-b,$ $\frac{a\pm \sqrt{a^2+4b}}2.$ Since $f(0)=0,$ $u+v=0.$ Then $u\sqrt{a^2+4b}=f(1). $ $\endgroup$ Commented Dec 4, 2021 at 17:09
  • 1
    $\begingroup$ You could present it in the following way: You want to study the sequence of remainders of the given sequence, after division by $k$. Observe that the same way that the recurrence allows you to compute $f(n+2)$ from $f(n+1)$ and $f(n)$, we can compute $f(n)$ from $f(n+2)$, $f(n+1)$. But more importantly, if we are told the remainders of $f(n+2)$ and $f(n+1)$ modulo $k$, then we can compute the remainder of $f(n)$ modulo $k$ since $\gcd(b,k)=1$. This observation is nearly all you need. ... $\endgroup$ Commented Dec 4, 2021 at 17:51
  • 1
    $\begingroup$ Next it is all about considering what values can have the remainders, modulo $k$, of two consecutive terms of the sequence. There are only $k^2$ pairs of remainders. So, eventually they start repeating. Now, it could be that there is a chunk of pairs are the beginning and the cycling only starts later. However, the fact that the recurrence of remainders can also be computed backward, it means that the loop also works back. So, the repetition starts from the beginning of the sequence. $\endgroup$ Commented Dec 4, 2021 at 17:53
  • 1
    $\begingroup$ A knowledge that I am assuming you have is that if $\gcd(k,b)=1$, then for every remainder $y$ modulo $k$, there is a unique remainder $x$, such that the remainder of $bx$ modulo $k$ is $y$. $\endgroup$ Commented Dec 4, 2021 at 17:57
  • 1
    $\begingroup$ And well, the closing blow to the problem is that the first pair of remainder is $(f(1)\mod{k}, f(0)\mod{k})$, where $f(0)\mod{k}=0$. So, every time this pair of remainders reappears, we get a remainder $0$ modulo $k$. $\endgroup$ Commented Dec 4, 2021 at 18:04

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.