Question

Let $f(a, b)$ be a function with the following properties for all positive integers $a \neq b$:

$f(1, 2) = f(2, 1)$ $f(a, b) + f(b, a) = 0$ $f(a + b, b) = f(b, a) + b$

Compute:

$\sum_{i=1}^{2019} f(4^i - 1, 2^i) + f(4^i + 1, 2^i)$

Answer 1

2^{2021}-6

Answer 2

The function $f(a, b)$ has the properties:

1. $f(1, 2) = f(2, 1)$
2. $f(a, b) + f(b, a) = 0 \implies f(a, b) = -f(b, a)$
3. $f(a + b, b) = f(b, a) + b$

From (1) and (2), $f(1, 2) = -f(1, 2) \implies 2f(1, 2) = 0 \implies f(1, 2) = 0$. Also, $f(2, 1) = 0$.

From (3), substitute $f(b, a) = -f(a, b)$: $f(a+b, b) = -f(a, b) + b$. Let $X = a+b$, then $a = X-b$. So, $f(X, b) = -f(X-b, b) + b$ for $X > b$. Applying this repeatedly: $f(X, b) = -(-f(X-2b, b) + b) + b = f(X-2b, b)$. This implies $f(a, b) = f(a-2b, b) = f(a-4b, b) = \dots$. Let $a = qb + r$, where $q = \lfloor a/b \rfloor$ and $r = a \pmod b$.

• If $q$ is even, $f(a, b) = f(r, b)$.
• If $q$ is odd, $f(a, b) = b - f(r, b)$.

If $r=0$, i.e., $a$ is a multiple of $b$: Using $f(2, 1) = 0$, where $q=2$ (even) and $r=0$, suggests $f(0, 1) = 0$. Using $f(3, 1) = f(1+2, 1) = f(2, 1) + 1 = 0+1=1$, where $q=3$ (odd) and $r=0$, suggests $1 = 1 - f(0, 1)$, implying $f(0, 1) = 0$. So, we assume $f(0, b) = 0$ for any $b$. Thus, if $a$ is a multiple of $b$:

• If $q = a/b$ is even, $f(a, b) = 0$.
• If $q = a/b$ is odd, $f(a, b) = b$.

We need to compute $S = \sum_{i=1}^{2019} (f(4^i - 1, 2^i) + f(4^i + 1, 2^i))$.

1. Evaluate $f(4^i - 1, 2^i)$: Let $a = 4^i - 1$ and $b = 2^i$. Since $i \ge 1$, $a > b$. $a = (2^i)^2 - 1$. The quotient $q = \lfloor ( (2^i)^2 - 1 ) / 2^i \rfloor = \lfloor 2^i - 1/2^i \rfloor = 2^i - 1$. The remainder $r = (2^i)^2 - 1 \pmod{2^i} = 2^i - 1$. Since $q = 2^i - 1$ is always odd for $i \ge 1$: $f(4^i - 1, 2^i) = b - f(r, b) = 2^i - f(2^i - 1, 2^i)$. Now, evaluate $f(2^i - 1, 2^i)$. Let $a' = 2^i - 1$ and $b' = 2^i$. Here $a' < b'$. $f(a', b') = -f(b', a') = -f(2^i, 2^i - 1)$. For $f(2^i, 2^i - 1)$, let $A = 2^i$ and $B = 2^i - 1$. $A > B$. $A = 1 \cdot B + 1$. So $q' = 1$ (odd), $r' = 1$. $f(2^i, 2^i - 1) = B - f(r', B) = (2^i - 1) - f(1, 2^i - 1)$. For $f(1, 2^i - 1)$, let $A'' = 1$ and $B'' = 2^i - 1$. Here $A'' < B''$. $f(1, 2^i - 1) = -f(2^i - 1, 1)$. For $f(2^i - 1, 1)$, let $A''' = 2^i - 1$ and $B''' = 1$. $A''' > B'''$. $q''' = (2^i - 1)/1 = 2^i - 1$ (odd for $i \ge 1$), $r''' = 0$. So, $f(2^i - 1, 1) = B''' = 1$. Therefore, $f(1, 2^i - 1) = -1$. Substitute back: $f(2^i, 2^i - 1) = (2^i - 1) - (-1) = 2^i$. Thus, $f(2^i - 1, 2^i) = -2^i$. Finally, $f(4^i - 1, 2^i) = 2^i - (-2^i) = 2 \cdot 2^i = 2^{i+1}$. This formula holds for $i > 1$. For $i=1$: $f(4^1 - 1, 2^1) = f(3, 2) = 2^1 - f(1, 2) = 2 - 0 = 2$. So for $i=1$, $f(4^i - 1, 2^i) = 2^i$. For $i > 1$, $f(4^i - 1, 2^i) = 2^{i+1}$.

2. Evaluate $f(4^i + 1, 2^i)$: Let $a = 4^i + 1$ and $b = 2^i$. Since $i \ge 1$, $a > b$. $a = (2^i)^2 + 1$. The quotient $q = \lfloor ( (2^i)^2 + 1 ) / 2^i \rfloor = \lfloor 2^i + 1/2^i \rfloor = 2^i$. The remainder $r = (2^i)^2 + 1 \pmod{2^i} = 1$. Since $q = 2^i$ is always an even number for $i \ge 1$: $f(4^i + 1, 2^i) = f(r, b) = f(1, 2^i)$. For $f(1, 2^i)$, let $a' = 1$ and $b' = 2^i$. Here $a' < b'$. $f(1, 2^i) = -f(2^i, 1)$. For $f(2^i, 1)$, let $A = 2^i$ and $B = 1$. $A > B$. $q' = 2^i/1 = 2^i$ (even for $i \ge 1$), $r' = 0$. So, $f(2^i, 1) = 0$. Therefore, $f(1, 2^i) = -0 = 0$. Thus, $f(4^i + 1, 2^i) = 0$ for all $i \ge 1$.

3. Compute the sum: $S = \sum_{i=1}^{2019} (f(4^i - 1, 2^i) + f(4^i + 1, 2^i))$ $S = \sum_{i=1}^{2019} (f(4^i - 1, 2^i) + 0)$ $S = f(4^1 - 1, 2^1) + \sum_{i=2}^{2019} f(4^i - 1, 2^i)$ $S = 2 + \sum_{i=2}^{2019} 2^{i+1}$ The sum is $2 + (2^{2+1} + 2^{3+1} + \dots + 2^{2019+1})$ $S = 2 + (2^3 + 2^4 + \dots + 2^{2020})$ The terms $(2^3 + 2^4 + \dots + 2^{2020})$ form a geometric series with first term $a = 2^3 = 8$, common ratio $r=2$, and number of terms $n = 2020 - 3 + 1 = 2018$. The sum of this geometric series is $8 \frac{2^{2018} - 1}{2 - 1} = 8(2^{2018} - 1) = 2^3 \cdot 2^{2018} - 2^3 = 2^{2021} - 8$. Therefore, $S = 2 + (2^{2021} - 8) = 2^{2021} - 6$.