MathDB

2

Part of 2020 Spain Mathematical Olympiad

Problems(1)

f(1)=1, f(n)=f(n/2) for n even, f(n) = f(n-1) + (-1)^f(n-1) for n odd.

Source: Spain Mathematical Olympiad 2020 P2

7/14/2020
Consider the succession of integers {f(n)}n=1∞\{f(n)\}_{n=1}^{\infty} defined as:
∙\bullet f(1)=1f(1) = 1. ∙\bullet f(n)=f(n/2)f(n) = f(n/2) if nn is even. ∙\bullet If n>1n > 1 odd and f(n−1)f(n-1) odd, then f(n)=f(n−1)−1f(n) = f(n-1)-1. ∙\bullet If n>1n > 1 odd and f(n−1)f(n-1) even, then f(n)=f(n−1)+1f(n) = f(n-1)+1.
a) Compute f(22020−1)f(2^{2020}-1).
b) Prove that {f(n)}n=1∞\{f(n)\}_{n=1}^{\infty} is not periodical, that is, there do not exist positive integers tt and n0n_0 such that f(n+t)=f(n)f(n+t) = f(n) for all n≥n0n \geq n_0.
recurrence relationSpain