MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was trying to solve one particular problem and to settle that problem I need to solve this problem, and it goes like this (sorry in advance for I still do not know LaTex symbolism so I will try to type it in the old-fashioned way):

If we have system of infinite number of equations that looks like this:

p(3)q(3) - 3p(2)q(2) + 2p(1)q(1)=0

p(4)q(4) - 3p(3)q(3) + 2p(2)q(2)=0

. . .

p(k+2)q(k+2) - 3p(k+1)q(k+1) + 2p(k)q(k)=0

. . .

,where p(k) and q(k) are natural numbers, not equal to 1 and not equal to 2, for every natural number k.

My question is as in title of the question: Does this system have a solution, or, in other words, do there exist two integer sequences p(k) and q(k), strictly greater than number 2 for every natural number k, such that they are solutions of this system?

share|cite|improve this question
P.S. Of course, the sequences p(k) and q(k) are not constant sequences. – Antisha Jan 21 '13 at 14:56
I removed the open-problem tag as this is rather only to be used for (well-)known open problems. – user9072 Jan 21 '13 at 15:06
up vote 8 down vote accepted

The $p_k$ and $q_k$ always appear together so let us for the moment write $a_k= p_kq_k$ (I will come back to the condition later).

Then your system can be rewritten as $a_{i+2} = 3a_{i+1} - 2a_i$ for $i$ a positive integer. Now if you pick any two starting values $0 \lt a_1 \lt a_2$ you directly get from these equations a recursively definied sequence of positive integers $a_i$.

Now, you want in addition that $a_i = p_i q_i$ with $p_i,q_i \ge 3$. To get this notice that if $d$ divides both $a_{i+1}$ and $a_i$ then it also divides $a_{i+2}$. So pick your $a_1$ and $a_2$ such that the have a greatest common divisor that is the product of two positive integers at least $3$, say take $a_1=9$ and $a_2=18$. Then you can always factor $a_i$ as $a_i=p_i q_i$ with the condition you want.

Added in view of comments by OP, based mainly on comments by Emil Jeřábek and Barry Cipra (answer now in CW mode):

If one wishes to further analyse the possible solutions, one can notice that the above mentioned recurrence can be solved explicitly and the solutions are of the form $u2^i + v$.

In particular, one can note that successive terms of the sequence $a_i$ are relatively co-prime if and only if $v$ is odd and co-prime to $u$.

By a result of Selfridge it is know that for $v=1$ and $u=78557$ the sequence $u2^i + v$ never takes a prime value, and indeed the terms are always divisible by one of $3,5,7,13,19,37,73$.

Thus the terms of this sequence $78557 \cdot 2^n + 1$, with $i \ge 1$, always admits a decomposition as requested by OP, as a product of two numbers at least $3$.

I guess, but did not check, the proof of Selfridge's result is based on covering congruences, a method alluded to by ARupinski. That is one covers the integers by a finite set of congruence classes and then checks the different finitely many cases individually.

share|cite|improve this answer
Since $x^2-3x+2=(x-1)(x-2)$, solutions of the recurrence are of the form $a_i=u2^i+v$ for constants $u,v$. – Emil Jeřábek Jan 21 '13 at 15:16
Thank you people, that was helpful. I must ask now does this system have a solution if we set a(1) to have the form: a(1)= 2^(c) + 2^(c-1) + ... + 2 + 1, for some constant c, c is a natural number strictly greater than 2 – Antisha Jan 21 '13 at 15:33
If you consider the description given by EJ and take the difference, you can note that any common divisor will divide $u 2^k$. So you choose $v$ odd and coprime to $u$ for successive terms always coprime. The question is know can you choose $u,v$ coprime (and $v$ odd) so that $u2^k + v$ is (provably) never prime. This is what I am not sure about from the top of my head (though I might overlook something simple). A strange way could be to take $v=1$ and $u=2^{17}$. Then this works if there are no other Fermat primes than the known ones. But perhaps there is a 'better' pair u,v. – user9072 Jan 21 '13 at 16:17
@Antisha: Ronald Graham's 1964 paper "A Fibonacci-like sequence of composite numbers" shows how to construct a linearly recurrent sequence all of whose entries are composite numbers using the Fibonacci recurrence. By modifying his approach it should be possible to find a covering sequence for this recurrence, (although there may be some complications I don't immediately see due to the fact that here the associated polynomial $x^2-3x+2$ factors while for the Fibonacci sequence the associated polynomial $x^2-x-1$ does not factor). – ARupinski Jan 21 '13 at 16:34
According to Section B21 in Richard Guy's Unsolved Problems in Number Theory, John Selfridge (in 1963) "discovered that one of $3,5,7,13,19,37,73$ always divides $78557\cdot2^n+1$." – Barry Cipra Jan 21 '13 at 17:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.