Sequences, Series and Recursions

Problems

Solutions

Solution: PRMO 2012, Q9

From $4^{X_1} = 5$ we get $X_1 = \log_4 5 = \dfrac{\ln 5}{\ln 4}$, and in general $X_i = \dfrac{\ln(i+4)}{\ln(i+3)}$.

Multiplying them all, every logarithm cancels against the next: $$X_1 X_2 \cdots X_{124} = \frac{\ln 5}{\ln 4}\cdot\frac{\ln 6}{\ln 5}\cdots\frac{\ln 128}{\ln 127} = \frac{\ln 128}{\ln 4} = \log_4 128.$$

Finally $128 = 2^7$ and $4 = 2^2$, so $$\log_4 128 = \frac{7}{2}.$$

Answer $7/2$

Solution: PRMO 2014, Q19

The identity to spot is $$\frac{x}{1-x} - x = \frac{x - x(1-x)}{1-x} = \frac{x^2}{1-x},$$ valid whenever $x \ne 1$, which the problem guarantees.

Summing it over all $2014$ values, $$\sum_{i=1}^{2014} \frac{x_i^2}{1-x_i} = \sum_{i=1}^{2014} \frac{x_i}{1-x_i} - \sum_{i=1}^{2014} x_i = 1 - 1 = 0.$$

Neither the number $2014$ nor the individual values played any part; any list with the two stated sums equal gives zero.

Answer 0

Solution: PRMO 2017, Q5

A geometric progression has $v^2=uw$. Neither $u$ nor $w$ can be zero: the equality $u^{40}=w^{60}$ would make both zero, contradicting $u>w$. Thus $uw=v^2>0$, so $u$ and $w$ have the same sign. The common value $K=u^{40}=w^{60}$ is positive. It cannot equal $1$, because then $|u|=|w|=1$ and the common sign would give $u=w$. Also $n\ne0$, since $v^0=1$ could not equal $K$. Write $L = \log K \ne 0$ and take logarithms of absolute values: $$40 \log|u| = n \log|v| = 60 \log|w| = L,$$ so $$\log|u| = \frac{L}{40}, \qquad \log|v| = \frac{L}{n}, \qquad \log|w| = \frac{L}{60}.$$

A geometric progression has $v^2 = uw$. Taking absolute values of both sides preserves that, since $|v^2| = |v|^2$ and $|uw| = |u||w|$, so $|v|^2 = |u||w|$ and the logarithms are in arithmetic progression: $$2\log|v| = \log|u| + \log|w|, \qquad \frac{2L}{n} = \frac{L}{40} + \frac{L}{60}.$$ Cancelling $L$ and adding the fractions, $$\frac2n = \frac{3 + 2}{120} = \frac{1}{24}, \qquad n = 48.$$

In words, $n$ is the harmonic mean of $40$ and $60$, which is what an arithmetic progression of logarithms always produces from equal powers.

Answer 48

Solution: PRMO 2017, Q6

The key identity is $$\frac{1}{n(n+1)(n+2)} = \frac12\left(\frac{1}{n(n+1)} - \frac{1}{(n+1)(n+2)}\right),$$ which one checks by putting the right-hand side over a common denominator: the numerator is $\tfrac12\bigl((n+2) - n\bigr) = 1$.

Summing from $n = 1$ to $9$, every interior term cancels against its neighbour and only the ends survive: $$\sum_{n=1}^{9} \frac{1}{n(n+1)(n+2)} = \frac12\left(\frac{1}{1 \cdot 2} - \frac{1}{10 \cdot 11}\right) = \frac12 \cdot \frac{54}{110} = \frac{27}{110}.$$

Since $110 = 2 \cdot 5 \cdot 11$ shares no factor with $27$, the fraction is already in lowest terms, so $p = 27$, $q = 110$ and $$q - p = 83.$$

Answer 83

Solution: PRMO 2017, Q16

Let the ratio be $r$. It is rational, since consecutive terms are integers, so write $r = p/q$ in lowest terms with $p \ne q$. Reversing the progression if necessary, take $p > q$, so the terms increase.

For the fifth term $a r^4 = a p^4/q^4$ to be an integer with $\gcd(p, q) = 1$, the first term $a$ must be a multiple of $q^4$, say $a = cq^4$. The five terms are then $$cq^4, \quad cq^3p, \quad cq^2p^2, \quad cqp^3, \quad cp^4,$$ all integers automatically.

Now impose the two-digit range. The smallest term is at least $10$ and the largest at most $99$, so $$cq^4 \ge 10, \qquad cp^4 \le 99, \qquad \text{hence} \qquad \left(\frac{p}{q}\right)^4 \le \frac{99}{10} < 10.$$ Since $\tfrac{99}{10} < 16 = 2^4$, that gives $p/q < 2$. In particular $q$ cannot be $1$, since $p > q$ would then make $p/q$ at least $2$; so $q \ge 2$. And $cp^4 \le 99$ with $c \ge 1$ gives $p^4 \le 99$, so $p \le 3$. The only coprime pair with $3 \ge p > q \ge 2$ is $(p,q) = (3,2)$, and then $cq^4 = 16c \ge 10$ and $cp^4 = 81c \le 99$ force $c = 1$.

The progression is therefore $$16, \quad 24, \quad 36, \quad 54, \quad 81,$$ five distinct two-digit numbers, and its middle term is $36$.

Answer 36

Solution: PRMO 2019, Q3

Write $P_n = x_1 x_2 \cdots x_n$, so that the rule reads $x_{n+1} = 1 + P_n$. For $n \ge 2$ this gives $P_{n-1} = x_n - 1$, and therefore $$P_n = P_{n-1}\, x_n = (x_n - 1)x_n.$$ Substituting back, $$x_{n+1} = 1 + x_n(x_n - 1) = x_n^2 - x_n + 1 \qquad (n \ge 2).$$

That is all we need. From $x_5 = 43$, $$x_6 = 43^2 - 43 + 1 = 1849 - 42 = 1807.$$ Factorising, $1807 = 13 \times 139$, and $139$ is prime, since it is divisible by none of $2$, $3$, $5$, $7$, $11$ and $13^2 = 169$ already exceeds it. The largest prime factor is $139$, whose digits sum to $1 + 3 + 9 = 13$.

Recovering $x_1$ is possible but unnecessary, and that is the lesson. Running the one-step rule backwards, $x_5 = 43$ gives $x_4 = 7$, then $x_3 = 3$, $x_2 = 2$ and $x_1 = 1$, each from a quadratic with one positive root. None of that was needed, because the rule steps from $x_5$ to $x_6$ directly. Whenever a recursively defined sequence is pinned down by one of its later values, look for a rule connecting consecutive terms before trying to unwind the whole thing back to the start.

Answer 13

Solution: PRMO 2019, Q7

Measure time $t$ in minutes after noon, when both hands point at $12$. The minute hand turns $360^{\circ}$ per hour, so it is at $6t$ degrees; the hour hand turns $30^{\circ}$ per hour, so it is at $\tfrac12 t$ degrees. The angle the minute hand has gained is $$6t - \tfrac12 t = \tfrac{11}{2}\,t,$$ which increases steadily from $0$ to $330^{\circ}$ as $t$ runs from $0$ to $60$.

The hands are perpendicular when this gain is $90^{\circ}$ or $270^{\circ}$, both of which occur in range: $$\tfrac{11}{2}t = 90 \implies t = \frac{180}{11}, \qquad \tfrac{11}{2}t = 270 \implies t = \frac{540}{11}.$$ Their difference is $$\frac{540 - 180}{11} = \frac{360}{11} = 32 + \frac{8}{11}.$$ So $a = 32$, $b = 8$, $c = 11$, and since $\gcd(8,11) = 1$ and $8 < 11$ this is the required reduced form. Hence $a + b + c = 51$.

Answer 51

Solution: IOQM 2020, Q3

A sum like this one is not meant to be evaluated term by term, and the shape of the numerator is the hint. Since $k^2 + k = k(k+1)$, the denominator is $k^2(k+1)^2$, and the numerator $2k+1$ is exactly $(k+1)^2 - k^2$. Writing the term with that in mind, $$\frac{2k+1}{(k^2+k)^2} = \frac{(k+1)^2 - k^2}{k^2 (k+1)^2} = \frac{1}{k^2} - \frac{1}{(k+1)^2},$$ where the last step is just splitting the fraction and cancelling.

Each term is now the difference of two consecutive members of the sequence $1/k^2$, so when we add them from $k=1$ to $k=N$ every interior quantity is created once and destroyed once, and only the two ends survive: $$\sum_{k=1}^{N} \frac{2k+1}{(k^2+k)^2} = 1 - \frac{1}{(N+1)^2}.$$

Setting this against the given value $0.9999$, which is $1 - \tfrac{1}{10000}$, we need $(N+1)^2 = 10000$, so $N + 1 = 100$ and $N = 99$.

Answer 99

Solution: IOQM 2025 Part SEP, Q28

Group the $2n$ terms in consecutive pairs. For each $j$ the pair contributes $$-(2j-1)^2 + (2j)^2 = (2j - (2j-1))(2j + (2j-1)) = 4j - 1,$$ so $$\sum_{k=1}^{2n} (-1)^k k^2 = \sum_{j=1}^{n} (4j-1) = 4 \cdot \frac{n(n+1)}{2} - n = 2n^2 + n = n(2n+1).$$

The inequality $n(2n+1) < 100$ therefore holds for $n = 6$, where the value is $78$, and fails at $n = 7$, where it is $105$. Since $n(2n+1)$ increases with $n$, the answer is $6$.

Answer 6

Solution: PRMO 2013, Q2

Rationalise the general term of $S_n$: $$\frac{1}{\sqrt{k+1} + \sqrt k} = \frac{\sqrt{k+1} - \sqrt k}{(k+1) - k} = \sqrt{k+1} - \sqrt k.$$ Summing from $k = 0$ to $n$, everything cancels except the ends: $$S_n = \sqrt{n+1} - \sqrt0 = \sqrt{n+1}.$$

Now the outer sum. Since $S_n + S_{n-1} = \sqrt{n+1} + \sqrt n$, the same rationalisation applies again: $$\frac{1}{S_n + S_{n-1}} = \sqrt{n+1} - \sqrt{n},$$ and summing from $n = 1$ to $99$ telescopes once more: $$\sqrt{100} - \sqrt1 = 10 - 1 = 9.$$

Two telescopes for the price of one rationalisation. The second is available only because the first collapsed $S_n$ into a single square root, which is the point of the construction.

Answer 9

Solution: PRMO 2017, Q11

Write $T = n\pi$ and use the sum-to-product identities on the difference: $$\sin\frac{x+T}{3} - \sin\frac{x}{3} = 2\cos\frac{2x+T}{6}\,\sin\frac{T}{6},$$ $$\cos\frac{3(x+T)}{10} - \cos\frac{3x}{10} = -2\sin\frac{3(2x+T)}{20}\,\sin\frac{3T}{20}.$$ So the condition $f(x+T) = f(x)$ for all $x$ says $$2\sin\frac{T}{6}\cos\frac{2x+T}{6} = 2\sin\frac{3T}{20}\sin\frac{3(2x+T)}{20} \qquad \text{for all } x.$$

Now compare least periods. A sine or cosine wave that is not constant has a least positive period, namely $2\pi$ divided by whatever multiplies $x$ inside it, and two functions that are equal at every $x$ are the same function and so have the same least period. That is the whole of the argument.

If the amplitude $2\sin\tfrac T6$ were not zero, the left side would be a wave of least period $6\pi$; if $2\sin\tfrac{3T}{20}$ were not zero, the right side would be a wave of least period $\tfrac{20\pi}{3}$. But $6\pi \ne \tfrac{20\pi}{3}$, so they cannot both be non-zero. And if just one were zero, that side would be identically zero and so would the other, forcing its amplitude to zero as well. So both amplitudes vanish: $$\sin\frac{n\pi}{6} = 0 \quad\text{and}\quad \sin\frac{3n\pi}{20} = 0.$$

The first says $6 \mid n$. The second says $20 \mid 3n$, and since $\gcd(3,20) = 1$ that means $20 \mid n$. Hence $n$ is a multiple of $\operatorname{lcm}(6,20) = 60$, and $n = 60$ works, because $60\pi$ is $10$ periods of the first wave and $9$ of the second.

Answer 60

Solution: PRMO 2017, Q14

Write $m = [x]$ and $f = \{x\}$, so $x = m + f$ with $0 \le f < 1$. For $f$, $m$, $x$ to be a geometric progression all three must be non-zero, so $m \ge 1$ and $f > 0$, and the middle term squared is the product of the outer two: $$m^2 = f(m+f), \qquad \text{that is} \qquad f^2 + mf - m^2 = 0.$$ Solving for the positive root, $$f = \frac{-m + \sqrt{5m^2}}{2} = m \cdot \frac{\sqrt5 - 1}{2}.$$

Now use $f < 1$, and no decimal is needed. If $m \ge 2$ then $f \ge 2 \cdot \tfrac{\sqrt5-1}{2} = \sqrt5 - 1 > 1$, since $\sqrt 5 > 2$. So $m = 1$. Then $$f = \frac{\sqrt5 - 1}{2}, \qquad x = 1 + f = \frac{1 + \sqrt5}{2} = \varphi,$$ the golden ratio, whose defining property $\varphi^2 = \varphi + 1$ is exactly the progression condition in disguise.

Finally we need the least $n$ with $\varphi^n > 100$. Multiply a term $A\varphi+B$ by $\varphi$. Since $\varphi^2=\varphi+1$, the result is $$(A\varphi+B)\varphi=(A+B)\varphi+A.$$ So the coefficient pair $(A,B)$ becomes $(A+B,A)$ at the next power. Starting from $\varphi^2=\varphi+1$, the powers needed are $$\begin{array}{c|rrrrrrrrr} k&2&3&4&5&6&7&8&9&10\\ \hline A&1&2&3&5&8&13&21&34&55\\ B&1&1&2&3&5&8&13&21&34 \end{array}$$ In particular $\varphi^9=34\varphi+21$ and $\varphi^{10}=55\varphi+34$. Exact bounds on $\varphi$ settle both. Since $\left(\tfrac{11}{5}\right)^2 = \tfrac{121}{25} < 5$ we have $\sqrt5 > \tfrac{11}{5}$ and so $\varphi > \tfrac85$; and $\sqrt5 < 3$ gives $\varphi < 2$. Hence $$\varphi^9 = 34\varphi + 21 < 68 + 21 = 89 < 100,$$ $$\varphi^{10} = 55\varphi + 34 > 55 \cdot \tfrac85 + 34 = 122 > 100.$$ So $\varphi^9 < 100 < \varphi^{10}$ and the answer is $$n = 10.$$

Answer 10

Solution: PRMO 2018, Q16

On the smaller list $1,2,3,4$, the odd pair-sums are $3,5,5,7$ and the even ones are $4,6$. Their difference is $20-10=10=1+2+3+4$. The ordinary total appearing here suggests that a signed count may cancel most of the pair contributions. The quantity asked for is $$T = \sum_{1 \le i < j \le 10} (i+j)\,(-1)^{i+j+1},$$ since a pair with $i+j$ odd contributes $+(i+j)$ and one with $i+j$ even contributes $-(i+j)$. Writing $a_i = (-1)^i$, the sign is $-a_ia_j$, so $$T = -\sum_{i<j}(i+j)\,a_ia_j.$$

Now evaluate that sum by turning it into a sum over ordered pairs. For each unordered pair the two orderings contribute $i\,a_ia_j$ and $j\,a_ja_i$, whose total is $(i+j)a_ia_j$. Hence $$\sum_{i<j}(i+j)a_ia_j = \sum_{i \ne j} i\,a_ia_j = \sum_{i} i\,a_i\left(S - a_i\right), \qquad S = \sum_{j=1}^{10} a_j.$$ Two evaluations finish it. First $S = -1+1-1+\cdots+1 = 0$, because the ten signs cancel in pairs. Second $a_i^2 = 1$, so the bracket collapses and $$\sum_{i<j}(i+j)a_ia_j = 0 - \sum_{i=1}^{10} i = -55.$$

Therefore $T = 55$.

The value $\sum i\,a_i = -1+2-3+\cdots+10 = 5$ never appeared, because it was multiplied by $S = 0$. That is the whole reason the answer is the plain triangular number $55$.

Answer 55

Solution: IOQM 2020, Q18

Whenever a sum of forty square roots is set as a competition problem, the roots are meant to disappear, so the first question to ask is whether the thing under each root is a square. Write $u = 1/k$ and $v = 1/(k+1)$, so that the expression is $1 + u^2 + v^2$, and try to match it against $(1 + u - v)^2$. Expanding that guess, $$(1 + u - v)^2 = 1 + u^2 + v^2 + 2u - 2v - 2uv,$$ so the guess is correct precisely when $u - v = uv$. That is exactly the identity we have, because $$\frac1k - \frac1{k+1} = \frac{1}{k(k+1)} = \frac1k \cdot \frac1{k+1}.$$ The coincidence is what makes the problem work, and it is worth noticing that it holds only for consecutive integers.

Since $1 + u - v$ is positive, the square root is exactly $$\sqrt{1 + \frac{1}{k^2} + \frac{1}{(k+1)^2}} = 1 + \frac1k - \frac{1}{k+1},$$ and the sum now separates into forty ones plus a telescoping tail: $$\sum_{k=1}^{40} \left(1 + \frac1k - \frac1{k+1}\right) = 40 + \left(1 - \frac{1}{41}\right) = 40 + \frac{40}{41}.$$

Matching this against $a + \tfrac{b}{c}$ with $b < c$ and $\gcd(b,c) = 1$ gives $a = 40$, $b = 40$ and $c = 41$, so $a + b = 80$.

Answer 80

Solution: IOQM 2020, Q20

Let there be $n$ women, all working at the same rate. The phrase that the group can build the wall in $45$ hours means that $n$ women working together for $45$ hours complete the job, so the wall represents exactly $45n$ woman-hours of labour, whatever $n$ happens to be.

Now account for how those hours were actually supplied. The women arrive one at a time at equal intervals, and each stays until the end, so the first woman works the longest and each subsequent one works a fixed amount less. Their working times therefore form an arithmetic progression, with first term the time $T$ worked by the first woman and last term the time worked by the last. We are told the first worked five times as long as the last, so the last term is $T/5$.

The total labour supplied is the sum of that progression, which for $n$ terms is the number of terms times the average of the first and last: $$n \cdot \frac{T + T/5}{2} = 45n.$$ The factor $n$ appears on both sides and cancels, which is the reason the problem never tells us how many women there were. What remains is $$\frac{6T}{10} = 45, \qquad \text{so} \qquad T = 75.$$

The first woman worked for $75$ hours.

Answer 75

Solution: IOQM 2023, Q10

The first few terms are $a_0=1$, $a_1=-4$ and $a_2=9$. The combination in the question begins $$a_1^2-a_0a_2=16-9=7.$$ The next term is $a_3=-4\cdot9-7(-4)=-8$, giving $$a_2^2-a_1a_3=81-32=49.$$ The individual terms are irregular, but this combination may have a much simpler rule. Substituting the recursion $a_{n+1} = -4a_n - 7a_{n-1}$ into the expression we are asked about gives $$a_n^2 - a_{n-1}a_{n+1} = a_n^2 - a_{n-1}(-4a_n - 7a_{n-1}) = a_n^2 + 4a_na_{n-1} + 7a_{n-1}^2.$$ Call the right-hand side $Q_n$. It is worth tracking $Q_n$ rather than the original expression, because it behaves so tidily. Using the recursion once more, $$Q_{n+1} = a_{n+1}^2 + 4a_{n+1}a_n + 7a_n^2 = a_{n+1}\bigl(a_{n+1} + 4a_n\bigr) + 7a_n^2,$$ which is $a_{n+1}\bigl(-7a_{n-1}\bigr) + 7a_n^2 = 7\,Q_n$, where the middle step used $a_{n+1} + 4a_n = -7a_{n-1}$.

So each step multiplies $Q$ by $7$, and the starting value is $$Q_1 = a_1^2 + 4a_1a_0 + 7a_0^2 = 16 - 16 + 7 = 7.$$ Hence $Q_n = 7^n$ for every $n \ge 1$, and in particular $$a_{50}^2 - a_{49}a_{51} = Q_{50} = 7^{50}.$$

The divisors of $7^{50}$ are $7^0, 7^1, \ldots, 7^{50}$, so there are $51$ of them.

Answer 51

Solution: IOQM 2026, Q16

Cross-multiplying, $$(a_{n+3} - a_{n+2})(a_n + a_{n+1}) = (a_{n+3} + a_{n+2})(a_n - a_{n+1}).$$ Both sides contain $a_{n+3}a_n$ and $-a_{n+2}a_{n+1}$, which cancel. What remains is $a_{n+3}a_{n+1} - a_{n+2}a_n = -a_{n+3}a_{n+1} + a_{n+2}a_n$, that is $$a_{n+1}a_{n+3} = a_n a_{n+2}.$$ So the product of two terms two places apart is the same number $k$ all the way along the sequence.

This $k$ is not zero. If it were, then $a_{55}a_{57} = 0$ with $a_{55} = 6$ would give $a_{57} = 0$, and $a_{56}a_{58} = 0$ would make $a_{56}$ or $a_{58}$ zero as well, next to $a_{57}$. Two neighbouring terms equal to $0$ make a denominator $a_n - a_{n+1}$ in the statement vanish. So no term is zero, and $$a_{n+4} = \frac{k}{a_{n+2}} = a_n,$$ which means the sequence repeats with period $4$.

Now $55 = 4 \cdot 13 + 3$, $66 = 4 \cdot 16 + 2$ and $77 = 4 \cdot 19 + 1$, so $a_3 = 6$, $a_2 = 2$ and $a_1 = 1$. Then $k = a_1a_3 = 6$ and $a_4 = k/a_2 = 3$. The sequence runs $1, 2, 6, 3, 1, 2, 6, 3, \ldots$, and no two neighbours are equal or opposite, so every fraction in the statement is defined.

Since $2026 = 4 \cdot 506 + 2$, $$N = 506\,(1 + 4 + 36 + 9) + 1 + 4 = 25300 + 5 = 25305,$$ and the sum of its digits is $2 + 5 + 3 + 0 + 5 = 15$.

Answer 15