Why do We Fall? To Rise Again!

Relevant wiki: Vieta Root Jumping

We use Vieta jumping method for solving this problem. Write $\frac{a+1}{b}+\frac{b+1}{a}=k \ \ \ \ \Longrightarrow \ \ \ \ a^2+a+b^2+b=kab \ \ \ \ \Longrightarrow \ \ \ \ a^2+(1-kb)a+b^2+b=0,$ where $k$ is a positive integer and last equation is a quadratic in terms of $a$ . Suppose that $(a_0, b_0)$ is a solution to the above quadratic, with $a_0 \ge b_0$ . If we let $b=b_0$ , equation has two solutions: $a=a_0$ and $a=a^*$ . By Vieta's formulas $a_0+a^*=kb_0-1$ and $a_0 a^*=b_0^2+b_0$ . Observe that $a^*=kb_0-1-a_0$ is an integer, and $a^*=\frac{b_0^2+b_0}{a_0}$ is positive.

Therewith, if $a_0 \ge \frac{b_0^2+b_0}{b_0}=b_0+1$ , then $a^*=\frac{b_0^2+b_0}{a_0} \le b_0$ , and we can choose $(a_1, b_1)=(b_0, a^*)$ as a solution to the equation. Note that $a_1+b_1=b_0+a^* < a_0 +b_0$ . In a similar manner, we can construct an another solution $(a_2, b_2)$ such that $a_2+b_2<a_1+b_1$ and etc.

Well-ordering principle tells us that we cannot repeat this procedure $\left( \color{#D61F06} \text{Fall!}\right)$ forever! Therefore, we will encounter a solution $(a_n, b_n)$ where $a_n< \frac{b_n^2+b_n}{b_n}=b_n+1$ , and we can no longer jump downwards. Now we must find the possible values of $(a_n, b_n)$ , i.e., possible values of the smallest solution. Note that $b_n \le a_n <b_n+1$ . It follows that $a_n=b_n$ , put this back in the original equation: $a_n^2+(1-k a_n)a_n+a_n^2+a_n=0 \ \ \ \ \Longrightarrow \ \ \ \ a_n+1-k a_n+a_n+1=0 \ \ \ \ \Longrightarrow \ \ \ \ k=\frac{2(a_n+1)}{a_n}$ Therefore $a_n \mid 2(a_n+1)$ or $a_n \mid 2(a_n+1)-2a_n=2$ , which gives $a_n=1, 2$ with $k=4, 3$ , respectively. So we must reconstruct solutions $\left( \color{#D61F06} \text{Rise!}\right)$ using two cases: $(a_n, b_n)=(1, 1)$ with $k=4$ and $(a_n, b_n)=(2, 2)$ with $k=3$ .

Notice that $(a_n, b_n)=(b_{n-1}, k b_{n-1}-a_{n-1}-1)$ and since $a_n=b_{n-1}$ we get $(a_{n-1}, b_{n-1})= (k a_n-b_n-1, a_n).$

Above recurrence relation gives the values of ${\color{#D61F06}a}$ less than $1000$ , for $(a_n, b_n)=(1, 1)$ with $k=4$ , as $({\color{#D61F06}1}, 1), ({\color{#D61F06}2}, 1), ({\color{#D61F06}6}, 2), ({\color{#D61F06}21}, 6), ({\color{#D61F06}77}, 21), ({\color{#D61F06}286}, 77).$ And gives the values of $a$ less than $1000$ , for $(a_n, b_n)=(2, 2)$ with $k=3$ , as $({\color{#D61F06}2}, 2), ({\color{#D61F06}3}, 2), ({\color{#D61F06}6}, 3), ({\color{#D61F06}14}, 6), ({\color{#D61F06}35}, 14), ({\color{#D61F06}90}, 35), ({\color{#D61F06}234}, 90), ({\color{#D61F06}611}, 234).$ Thus the answer is $1+2+3+6+14+21+35+77+90+234+286+611=\boxed{1380}$ .