BMO 1993, Round 1, Question 3

Hi,

First of all, I'd like to link the pdf of previous BMO competitions I am working on here. I am working on BMO1 1993, question 3, which is on the first page.

The question is as follows:

Unparseable latex formula:

[br]For each positive integer $c$, the sequence $u_n$ of integers is defined by $u_1 = 1$, $u_2 = c$, $u_n = (2n+1) u_{n−1}−(n^2 − 1) u_{n−2}$, $(n \geq 3)$. For which values of $c$ does this sequence have the property that $u_i$ divides $u_j$ whenever $i \leq j$? (Note: If $x$ and $y$ are integers, then $x$ divides $y$ if and only if there exists an integer $z$ such that $y$ = $xz$. For example, $x = 4$ divides $y = −12$, since we can take $z = −3$.)

So, I am struggling with this question. Please can someone give me hints as to how I find the certain values of $c$ such that $u_i$ divides $u_j$ for all $i \leq j$?

Thanks for the help!
(edited 2 years ago)
Original post by Ch4d3rz
Hi,

First of all, I'd like to link the pdf of previous BMO competitions I am working on here. I am working on BMO1 1993, question 3, which is on the first page.

The question is as follows:

Unparseable latex formula:

[br]For each positive integer $c$, the sequence $u_n$ of integers is defined by $u_1 = 1$, $u_2 = c$, $u_n = (2n+1) u_{n−1}−(n^2 − 1) u_{n−2}$, $(n \geq 3)$. For which values of $c$ does this sequence have the property that $u_i$ divides $u_j$ whenever $i \leq j$? (Note: If $x$ and $y$ are integers, then $x$ divides $y$ if and only if there exists an integer $z$ such that $y$ = $xz$. For example, $x = 4$ divides $y = −12$, since we can take $z = −3$.)

So, I am struggling with this question. Please can someone give me hints as to how I find the certain values of $c$ such that $u_i$ divides $u_j$ for all $i \leq j$?

Thanks for the help!

Just having my breakfast so not worked it through. Have you written out any simple sequences to see if you can spot a pattern? Then maybe think about a proof (or not) by ~induction. If you assume that all the terms up to n-1 are divisible by the preceding terms, then the first term of the recurrence equation is trivially divisible. So then its up to thinking about the second term. The dots multiplier will probably be worth thinking about. Even just thinking about u[3] will give rule some stuff out.

Id note that often questions like these are more about proving sequences dont exist and often there are no sequences or at most one or two that satisfy the given properties.
(edited 2 years ago)
Original post by mqb2766
Just having my breakfast so not worked it through. Have you written out any simple sequences to see if you can spot a pattern? Then maybe think about a proof (or not) by ~induction. If you assume that all the terms up to n-1 are divisible by the preceding terms, then the first term of the recurrence equation is trivially divisible. So then its up to thinking about the second term. The dots multiplier will probably be worth thinking about. Even just thinking about u[3] will give rule some stuff out.

Id note that often questions like these are more about proving sequences dont exist and often there are no sequences or at most one or two that satisfy the given properties.

Thank you, that's a very useful angle to attack this problem!
Original post by Ch4d3rz
Thank you, that's a very useful angle to attack this problem!

Often you'll find there is an "obvious" way to attack the problem using algebra/modulo-type arithmetic, but really thats after doing the problem and often the key thing is to just get stuck in. Working out what to prove is often the hard thing, whether that is that there are no such c or all c or even c or ...

Post what you've tried if you get anywhere (or not).
(edited 2 years ago)
U_1 = 1U_2 = CU_3 = 7C - 8Hence C | 7C - 8So C | 8So C is 1,2 4 or 8.Checking the first few terms of each of these shows that C = 1,8 don’t work so C = 2 or 4Write out a few terms for C = 2 and C = 4You will notice that for C = 4, U_n = (n 2)U_n-1, and that for C = 2, U_n = (n)U_n-1Now prove these by induction and write some fancy maths statements and ur done