Looking for generating function of $\sum_{k=0}^{\infty} \frac{a^k}{1-x^k}$

Asked Aug 25 '23 at 11:53

Active Aug 25 '23 at 12:22

Viewed 103 times

Wondering if anyone knows how to find a generating function or a nice clean formula for

$$\sum_{k=0}^{n} { {n}\choose{k} } (a^k \bmod q)$$

Multiplying by $x^n$ and summing over $n$ gives the below as a generating function, maybe there is a simple form for this?

$$\sum_{k=0}^{\infty} \frac{a^k}{1-x^k}.$$

edited Aug 25 '23 at 12:22

Shaun

asked Aug 25 '23 at 11:53

mtheorylord

1

$\sum_{k=0}^n {n \choose k} a^k = (1+a)^n$ without the need for all that. Also $\frac{a^k}{1-x^k}$ is no good when $k=0$. – aschepler Aug 25 '23 at 12:47
Let $f(a,q) = \sum_{k=0}^{n} { {n}\choose{k} } (a^k \bmod q)$. Apparently, some special cases are $f(2,3)=3\cdot 2^{n-1}$, $f(2,4)=2n+1$, $f(2,6)=3\cdot 2^n-3$, $f(2,8)=2n^2+1$, $f(2,16)= (4n^3-6n^2+8n+3)/3$, $f(3,4)=2^{n+1}$, $f(3,6)=3\cdot 2^n-2$, $f(3,9)=3n+1$, $f(3,27)=(9n^2-3n+2)/2$. – Fabius Wiesner Aug 25 '23 at 12:50
@BillyJoe Yes, thank you. It has a surprising amount of structure – mtheorylord Aug 25 '23 at 12:53
See also this and this found with Approach Zero. – Fabius Wiesner Aug 25 '23 at 13:08
See also this related question. After reading the answer there, I conjecture that your sequence satisfies a recurrence $a(n)=2(m \bmod 2)a(n-m)+\sum_{k=1}^{m-1}{m \choose k}(-1)^{k+1}a(n-k)$ where $m=ord_{q}(a)$. – Fabius Wiesner Aug 27 '23 at 21:06

0 Answers0