Solving Functional Equation from an Ordinary Generating Function

64 Views Asked by At

I was working with a friend on his CS homework, and one of his problems involved the following sequence: $$T(1) = 1; T(n) = T(n - 1) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) \text{for } n > 1$$ I tried using an ordinary generating function working as follows: \begin{align*} f(x) &= \sum_{n = 1}^\infty T(n)x^n = x + \sum_{n = 2}^\infty T(n - 1)x^n + \sum_{n = 2}^\infty T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)x^n \\ &= x + x\sum_{n = 1}^\infty T(n)x^n + \sum_{n = 2}^\infty T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)x^n \end{align*} For the rightmost sum, I split it up into even and odd terms and got the following: \begin{align*} \sum_{n = 2}^\infty T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)x^n &= \sum_{n = 1}^\infty T\left(\left\lfloor\frac{2n}{2}\right\rfloor\right)x^{2n} + \sum_{n = 1}^\infty T\left(\left\lfloor\frac{2n + 1}{2}\right\rfloor\right)x^{2n + 1} \\ &= \sum_{n = 1}^\infty T(n)x^{2n} + x\sum_{n = 1}^\infty T(n)x^{2n} \end{align*} Using our definition of $f$, I got the relation $f(x) = x + xf(x) + f(x^2) + xf(x^2)$. I have absolutely no idea how to proceed from here. I know that $f(x) = -\frac{1}{2}$ is our only constant solution, but that doesn't lead to a closed form for $T(n)$. I haven't worked all that much with OGEs, so I might have done something completely wrong in the beginning, but even so, is there a way to find any other solutions or to prove that $f(x) = -\frac{1}{2}$ is our only continuous solution to that functional equation?