2

In one of books for discrete mathematics i came across sum to calculate $$\sum_{k=0}^n \lceil \sqrt{n} \rceil$$ which was fairly easy, but this sum intrigued me what is generating function for $$\sum_{n=0}^\infty \lceil \sqrt{n} \rceil x^n $$ so from that i can easily calculate $$\sum_{n=0}^\infty x^n \sum_{k=0}^n \lceil \sqrt{k} \rceil $$

My attempt:

Our sequence looks like this $0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4 \dots$ We see, difference between adjancent positions is 0 or 1. Let's write it down: $0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, \dots$

First zero seems quite uncomfortable, so let's ignore it (but we will have to multiply final generating function by $x$).

So, now we deal with $1, 1, 0, 0, 1, 0, 0, 0, 0, 1, \dots$ Between adjancent ones there is: 0 zeros, then 2 zeros, then 4 zeros, 6 zeros and so on...

I can't really see some pattern here (how to pack zeros and ones in one sequence), i would really appreciate some hints or solutions to this, because it appears as really interesting problem. Cheers

Krzysztof Lewko
  • 2,312
  • Surely your series converges if $\left|x\right|<1$ because $\left\lceil \sqrt{n}\right\rceil <\sqrt{n}+1$ and $\sum_{n\geq1}\sqrt{n}x^{n}=\textrm{Li}_{-\frac{1}{2}}\left(x\right).$ – Marco Cantarini Apr 01 '15 at 20:24
  • @MarcoCantarini thanks for this comment, but we don't need to care about convergence of this generating function as long as we don't substitute any value for x. – Krzysztof Lewko Apr 01 '15 at 20:26
  • 1
    Yes, it was only to consider how big can be the radius of convergence for the generating function ;) – Marco Cantarini Apr 01 '15 at 20:30

1 Answers1

5

As far as I can tell, the answer can only be written in terms of the Jacobi theta functions (or the like). Specifically, we have

$$ \begin{align} \sum_{n=0}^\infty \lceil \sqrt{n} \rceil x^n & = x + 2x^2 + 2x^3 + 2x^4 + 3x^5 + 3x^6 + 3x^7 + 3x^8 + 3x^9 + \cdots \\ & = (x + x^2 + x^3 + \cdots) + (x^2 + x^3 + x^4 + \cdots) + (x^5 + x^6 + x^7 + \cdots) + \cdots \\ & = \frac{x}{1-x} + \frac{x^2}{1-x} + \frac{x^5}{1-x} + \cdots \\ & = \frac{x}{1-x} (1 + x + x^4 + x^9 + x^{16} + \cdots) \\ & = \frac{x}{1-x} \sum_{k=0}^\infty x^{k^2} \\ & = \Bigl(\frac{x}{1-x}\Bigr) \Bigl(\frac{\vartheta_3(0, x) - 1}{2}\Bigr) \end{align} $$

Don't know if this helps you at all.

Brian Tung
  • 34,160