How many times does a term appear in this sum?

Question

Let $F(a, b) = x^{a + b} + F(a, a + b) + F(b, a + b), x \in (0,\infty) -\{ 1 \}$ and $a, b \in \mathbb{N}$.

So $F(1, 2) = x^3 + F(1, 3) + F(2, 3) = x^3 + x^4 + x^5 + F(1, 4) + F(3, 4) + F(2, 5) + F(3, 5)$.
And the recursion continues infinitely.

How many times does the general term $x^k, k \geq 3$ appear in the infinite sum that emerges from the above stated recursive function? for the call $F(1, 2)$

So basically I just want the multiplier of the general term.
That is, if the sum is of form $S = \sum^{\infty}_{k = 3}a_kx^k$ then I want to find out the value of $a_k$ in terms of $k$ and constants.

It is easy to observe that each term appears at least once because the call $F(1, i)$ will add $x^i$ to the sum and also call $F(1, i + 1)$.

It might be easier to replace $x^{a+b}$ with $x^ay^b$ and then set $y=x.$ — Thomas Andrews, Jun 01 '21 at 20:45
That's not correct. In above example we already have $x^5$ two times — LegNaiB, Jun 01 '21 at 20:58
@LegNaiB, Oh, you're right. I missed that a $x^k$ can come from two different recursive calls. — Prasun Biswas, Jun 01 '21 at 20:59
My non-answer is now an answer. The coefficient of $x^n$ is $\frac{1}{2}\phi(n).$ — Thomas Andrews, Jun 01 '21 at 21:44

Thomas Andrews · Accepted Answer · 2021-06-02T18:30:05.383

Instead, write:

$$F_{a,b}(x,y)=x^ay^b + F_{a,a+b}(x,y)+F_{b,a+b}(x,y)$$

Then $F_{a,b}(x,x)=F(a,b)$ as you’ve defined it.

Let $H(x,y)=F_{1,2}(x,y).$

In particular, $x^ay^b$ only occurs if $a<b$ and $b-a\neq a.$

Also, there is at most one path to get $x^ay^b,$ since it comes from $F_{a,b-a}$ when $a<b-a$ and $ F_{b-a,a}$ when $a>b-a.$ so the coefficient of $x^ay^b$ is zero or $1.$

Show that $x^ay^b$ occurs in $H$ if and only if $0<a<b$ and $\gcd(a,b)=1.$ Roughly, this is because the reverse process is essential the Euclidean algorithm for the GCD.

This also means that the coefficient of $x^n$ (when $n>2$) in $H(x,x)$ is:

$$\sum_{\substack{a<b\\a+b=n\\\gcd(a,b)=1}}1=\frac12\phi(n)$$ where $\phi$ is Euler’s $\phi$ function.

This is because $\gcd(a,b)=1\iff \gcd(a,a+b)=\gcd(a,n)=1.$

How many times does a term appear in this sum?

1 Answers1