Generating functions and recursions smelling from 1000 km

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

6 users

TOPICS

No tags match your search

M

No tags match your search

M

Generating functions and recursions smelling from 1000 km

G H J

Reveal topic tags

counting techniques

college contests

generating functions

L

G H BBookmark kLocked kLocked NReply

Source: IMC 2022 Day 1 Problem 3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1182 posts

#1 h Aug 5, 2022, 11:06 PM

Y by

Let $p$ be a prime number. A flea is staying at point $0$ of the real line. At each minute,
the flea has three possibilities: to stay at its position, or to move by $1$ to the left or to the right.
After $p-1$ minutes, it wants to be at $0$ again. Denote by $f(p)$ the number of its strategies to do this
(for example, $f(3) = 3$ : it may either stay at $0$ for the entire time, or go to the left and then to the
right, or go to the right and then to the left). Find $f(p)$ modulo $p$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

28 posts

#2 h Aug 6, 2022, 6:04 AM • 1 Y

Y by Snark_Graphique

Firstly, note that
$f(p) = \sum_{k=0}^{\frac{p-1}{2}} \frac{(p-1)!}{k! \, k! \, (p-1-2k)!} \, .$ Here I scratched for about an hour thinking that I might need to apply Wilson's theorem here. But that was a failed attempt. Then I noticed that $f(p)$ is the constant term of
$P(x) = \left( x + \frac1x + 1 \right)^{p-1} \, .$ My initial idea was to use Roots of Unity filtering. That, too, was a failed attempt. Then I thought of taking the sum of $P(a)$ for every $a=1,2,\ldots, p-1$ . Let $c$ be the constant term of $P(x)$ .
$\begin{split} P(a) &= \left( a + \frac1a + 1 \right)^{p-1} = \left( a + a^{-1} + 1 \right)^{p-1} \\ &= c + a^{p-1} + a^{-p+1} + \sum_{j} c_j a^j \\ &= 2+c+\sum_{j} c_j a^j \end{split}$ Now, let's take the sum of $P(a)$ for $a \in \mathbb F _p^{\times}$ . Since $p$ is a prime, there is a primitive root $g$ modulo $p$ . Therefore, $\{ g, g^2, \ldots, g^{p-2}, g^{p-1}=1\} = \mathbb F _p^{\times}$ .
$\sum _{a \in \mathbb F _p^{\times}} a^j = \sum _{i=0}^{p-2} g^{ij} = \frac{g^{(p-1)j}-1}{g^j -1} = 0 \, .$ As a result,
$\sum _{a\in \mathbb F _p^{\times}} P(a) = (c+2)(p-1) + \sum _j c_j \sum _{i=0}^{p-2} g^{ij} = (c+2)(p-1) \, .$ Now, if $p\equiv-1 \mod 3$ , the polynomial $X^2+X+1$ is irreducible in $\mathbb F_p [X]$ , otherwise it has two roots in $\mathbb{F} _p [X]$ . (During the contest, I missed this part. Lord knows what was going through my head, I wrote $X^2+X+1$ is irreducible for every $p$ .)

If $p\equiv-1 \mod 3$ , $a+a^{-1}+1 = (a^2 + a + 1)a^{-1}$ is not $0$ for any $a\in \mathbb F _p^{\times}$ , so $P(a) = 1$ . Therefore, $\sum\limits _{a\in \mathbb F _p^{\times}} P(a) = p-1$ .

Otherwise, $a+a^{-1}+1 = (a^2 + a + 1)a^{-1}$ is $0$ for two values of $a$ . So $\sum\limits _{a\in \mathbb F _p^{\times}} P(a) = p-3$ .

$(c+2)(p-1) = \begin{cases} p-1 & \quad \text{ if } p\equiv-1 \mod 3 \\ p-3 & \quad \text{ if } p\equiv 1 \mod 3 \end{cases}$
From this, we get
$c = \begin{cases} -1 & \quad \text{ if } p\equiv-1 \mod 3 \\ 1 & \quad \text{ if } p\equiv 1 \mod 3 \end{cases}$
Of course, this is for $p > 3$ . So
$f(p) \mod p = \begin{cases} 0 & \quad \text{ if } p \in \{2,3\} \\ 1 & \quad \text{ if } p=3k+1 \\ p-1 & \quad \text{ if } p=3k-1 \end{cases}$

This post has been edited 1 time. Last edited by Kala_Para_Na, Aug 6, 2022, 6:06 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9022 posts

#3 h Aug 6, 2022, 7:35 AM • 3 Y

Y by MelonGirl, GHHardy911, Mango247

Kala_Para_Na wrote:

Firstly, note that
$f(p) = \sum_{k=0}^{\frac{p-1}{2}} \frac{(p-1)!}{k! \, k! \, (p-1-2k)!} \, .$ Here I scratched for about an hour thinking that I might need to apply Wilson's theorem here. But that was a failed attempt.

But not at all a dead end! Note that the summand is clearly congruent to $\binom{2k}{k}$ modulo $p$ , i.e.
$f(p) \equiv \sum_{k=0}^{\frac{p-1}{2}} \binom{2k}{k} \pmod{p}.$ Also note that $p \mid \binom{2k}{k}$ for $\frac{p}{2}<k<p$ . Hence, using the well-known $\sum_{k_1+k_2=s} \binom{2k_1}{k_1}\binom{2k_2}{k_2}=4^s$ , we get that
$f(p)^2 \equiv \sum_{k=0}^{p-1} 4^k \pmod{p}$ which is $1$ unless $p=3$ . In other words, our answer is either $1$ or $-1$ . But which one?
To find this, we need to be slightly more clever in our initial step and use generating functions, albeit in a completely different manner than in #2!
Indeed, note that if we write
$A(x)=\sum_{k=0}^{\frac{p-1}{2}} \binom{2k}{k}x^k,$ then $f(p) \equiv A(1) \pmod{p}$ . Now, as before we find that
$A(x)^2=\sum_{k=0}^{p-1} (4x)^k=\frac{1-(4x)^p}{1-4x}=\frac{(1-4x)^p}{1-4x}=(1-4x)^{p-1}$ as polynomials over $\mathbb{F}_p$ (using Little Fermat). Putting $x=1$ we recover our result about $f(p)^2$ . But what have we gained?
Note that polynomials over fields have at most two square roots. So
$A(x)=\pm (1-4x)^{\frac{p-1}{2}}$ for one of the two choices of the sign, but identically as a polynomial in $x$ . But of course comparing constant coefficients, we now see that actually $A(x)=(1-4x)^{\frac{p-1}{2}}$ and hence $f(p)=A(1)=(-3)^{\frac{p-1}{2}}=\left(\frac{-3}{p}\right)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8219 posts

#4 h Aug 6, 2022, 4:54 PM

Y by

@above I don't think your formula for $A(x)^2$ is correct after the $x^{(p-1)/2}$ term. For example the coefficient of $x^{p-1}$ should be $\binom{p-1}{(p-1)/2}^2$ .

Edit: actually, what you can do is since for $\frac{p-1}{2}<k\leq p-1$ we have $\binom{2k}{k}\equiv 0\mod p$ , so then we have that
$A(x)\equiv \sum_{k=0}^{p-1} \binom{2k}{k}x^k\mod p$ Which means that $A(x)^2\equiv \sum_{k=0}^{p-1} (4x)^k\mod p$ .

This post has been edited 2 times. Last edited by natmath, Aug 6, 2022, 5:00 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#5 h Aug 6, 2022, 9:32 PM

Y by

Note $f(p)=[x^0] (x+1+x^{-1})^{p-1}$

If $(x+1+x^{-1})^{p-1} = \sum\limits_{j=1-p}^{p-1} a_jx^j$ , then $\sum\limits_{x=1}^{p-1} (x+1+x^{-1})^{p-1} = \sum\limits_{j=1-p}^{p-1} a_j \sum\limits_{x=1}^{p-1} x^j$ .

Note $\sum\limits_{x=1}^{p-1} x^j\equiv -1(\bmod\; p)$ if $p-1\mid j$ and is 0 mod p otherwise.

Therefore, this sum is merely $-(a_{1-p}+a_{p-1}+a_0)=-(1+1+f(p))=-2-f(p) (\bmod\; p)$

On the other hand, recall $x^{p-1} \equiv 1(\bmod\; p)$ if $p\nmid x$ . Therefore, this sum is just the number of solutions to $x^2+x+1 \ne 0$ , which is $p-1 - \#(x^2+x+1=0)$ in $\mathbb{Z}_p$ . This is $p-1$ if $p\equiv 5(\bmod\; 6), p-2$ if $p=3$ and $p-3$ if $p\equiv 1(\bmod\; 6)$

Therefore, if $p=3, -2-f(p)\equiv -2$ so $f(p)\equiv 0(\bmod\; p)$

If $p\equiv -1(\bmod\; 6), -2-f(p)\equiv p-1$ so $f(p)\equiv -1(\bmod\; p)$

If $p\equiv 1(\bmod\; 6)$ then $f(p)\equiv 1(\bmod\; p)$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9022 posts

#6 h Aug 7, 2022, 2:33 PM • 1 Y

Y by natmath

natmath wrote:

@above I don't think your formula for $A(x)^2$ is correct after the $x^{(p-1)/2}$ term. For example the coefficient of $x^{p-1}$ should be $\binom{p-1}{(p-1)/2}^2$ .

Edit: actually, what you can do is since for $\frac{p-1}{2}<k\leq p-1$ we have $\binom{2k}{k}\equiv 0\mod p$ , so then we have that
$A(x)\equiv \sum_{k=0}^{p-1} \binom{2k}{k}x^k\mod p$ Which means that $A(x)^2\equiv \sum_{k=0}^{p-1} (4x)^k\mod p$ .

Yes, as I said I am of course using that $p \mid \binom{2k}{k}$ for $\frac{p}{2}<k<p$ and, again as I said, my identity for $A(x)^2$ is an identity as polynomials over $\mathbb{F}_p$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

572 posts

#7 h Aug 8, 2022, 10:03 AM

Y by

There will be $k$ left movements, $k$ right movements, and $p-2k$ staying in the same position.
Thus, $f(p) = \sum_{k=0}^{(p-1)/2} \frac{(p-1)!}{k! k! (p-1-2k)!}$
By wilson's, we have $(p-1-a)! = - \frac{1}{(p-1) \cdots (p-a)} = (-1)^{a-1} \frac{1}{a!} \pmod{p}$
Thus $f(p) = \sum_{k=0}^{(p-1)/2} \frac{-1}{ k! k! (-1)^{2k-1} \frac{1}{(2k)!} } = \sum_{k=0}^{(p-1)/2} \frac{(2k)!}{k! k!} = \sum_{k=0}^{(p-1)/1} \binom{2k}{k} \pmod{p}$
Then since $(1-4x)^{-1/2} = \sum_{k=0}^{\infty} \binom{-1/2}{k} (-4x)^{k} = \sum_{k=0}^{\infty} \binom{2k}{k} x^k$ we get $\binom{-1/2}{k} (-4)^k = \binom{2k}{k},$ and it easily follows that $\binom{2k}{k} = \binom{\frac{p-1}{2}}{k} (-4)^k \pmod{p}$ for $k \leq \frac{p-1}{2}.$
Thus, we have $\sum_{k=0}^{(p-1)/2} \binom{\frac{p-1}{2}}{k} (-4)^k = \boxed{ (-3)^{\frac{p-1}{2}} } \pmod{p}.$
Since $\left( \frac{-3}{p} \right) = \left( \frac{p}{3} \right),$ we finally have have
$f(p) = 0$ for $p=2,3$ and $f(p) = 1$ when $p \equiv 1 \pmod{3},$ and $f(p) = -1$ when $p \equiv 2 \pmod{3}.$

This post has been edited 1 time. Last edited by MelonGirl, Aug 8, 2022, 10:06 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

784 posts

#8 h Jan 25, 2024, 5:10 AM

Y by

Define the generating function $A(x) = \sum_{k \ge 0} a_kx^k$ . Then
$\begin{align*} \sum_{k \ge 0} f(k) x^k &= \sum_{k \ge 0} \sum_{n \ge 0} \binom{k-1}{n,n,k-1-2n} \\ &= \sum_{n \ge 0} \binom{2n}{n} \sum_{k \ge 0} \binom{k}{2n} x^k \\ &= \frac{1}{\sqrt{1-\frac{4x^2}{(1-x)^2}}} \\ &= \frac{1}{\sqrt{1-3x}} \cdot \frac{1}{\sqrt{1+x}} \\ &= \left(\sum_{n \ge 0} \binom{2n}{n} \left(\frac 34 x\right)^n\right) \cdot \left(\sum_{n \ge 0} \binom{2n}{n} \left(-\frac 14 x\right)^n\right). \end{align*}$
The only $x^p$ term in the expansion of this expression which isn't a multiple of $p$ is
$\binom{p-1}{(p-1)/2} \cdot \left(-\frac{3}{16}\right)^{(p-1)/2} \equiv (-3)^{(p-1)/2} \pmod p.$
Quick FLT and quadratic reciprocity along with confirming our edge cases $p=2,3$ gives us our answer
$\boxed{f(p) \pmod p \equiv \begin{cases} 1 & \text{if } p \equiv 1 \pmod 3 \\ -1 & \text{if } p \equiv 2 \pmod 3 \\ 0 & \text{if } p = 3 \end{cases}}$

This post has been edited 1 time. Last edited by shendrew7, Jan 25, 2024, 5:17 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

127 posts

#9 h Aug 2, 2024, 10:58 AM

Y by

Similar to CANBANKAN's solution, will post for storage. From now on, everything is considered modulo $p$ , and assume $p \ge 3$ .

As in the above solutions, we are interested in the coefficient next to $x^{p-1}$ in $F(x)=(1+x+x^2)^{p-1}$ .
Using the ROU filter we get:
$a_0+a_{p-1}+a_{2p-2}=\frac{1}{p-1}\sum_{i=0}^{p-2} F(\omega^i)$ where $\omega$ is the primitive root modulo $p$ .
Notice $a_0=a_{2p-2}=1$ . From the Fermat's theorem we get $F(x)=0,1$ , with $0$ occuring iff $1+x+x^2=0$ has a solution in $\mathbb{F}_p$ . This has $1+\left( \frac{-3}{p} \right)$ solutions.

Finally, the mentioned sum is just $p-1-(1+\left( \frac{-3}{p} \right))$ , giving the answer $\left( \frac{-3}{p} \right)$ , while you can check $p=2$ by hand.

This post has been edited 2 times. Last edited by triangle112, Aug 2, 2024, 11:04 AM
Reason: clarification

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8219 posts

#10 h Aug 2, 2024, 3:40 PM

Y by

We want to find the coefficient of $x^{p-1}$ in $(1+x+x^2)^{p-1}\in F_p((x))$ . Note that this is equal to $\frac{(1+x+x^2)^p}{1+x+x^2}$ . It is a corollary of freshman's dream that $(1+x+x^2)^p=1+x^p+x^{2p}$ when coefficients are taken $\mod p$ . So we want the coefficient of $x^{p-1}$ in
$\frac{1+x^p+x^{2p}}{1+x+x^2}$ $\frac{1-x+x^p-x^{p+1}+x^{2p}-x^{2p+1}}{1-x^3}$ If $p\equiv 0\mod 3$ , this is $0$
If $p\equiv 1\mod 3$ , this is $1$
If $p\equiv 2\mod 3$ , this is $-1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1714 posts

OronSH

#11 h Aug 25, 2024, 12:06 AM

Y by

We consider the generating function $(x^{-1}+1+x)^{p-1}.$ Setting $x=1,2,\dots,p-1$ and summing, each coefficient in the expanded form cancels, except for the $x^{-(p-1)},x^{p-1}$ and constant term. This is because for $p-1\nmid a$ we have $1^a+2^a+\dots+(p-1)^a\equiv g^a+g^{2a}+\dots+g^{(p-1)a}\equiv\frac{g^{pa}-g^a}{g^a-1}\equiv 0\pmod p$ where $g$ is a primitive root. Additionally the $x^{-(p-1)},x^{p-1}$ and constant coefficients are multiplied by $-1$ since we are adding $p-1$ copies of $1.$ However the $x^{-(p-1)}$ and $x^{p-1}$ coefficients are both originally $1.$ Thus if the sum of $(x^{-1}+1+x)^{p-1}$ over $x=1,2,\dots,p-1$ is $n\pmod p,$ the answer is $-n-2.$

Now $(x^{-1}+1+x)^{p-1}\equiv 1\pmod p$ unless $p\mid x^2+x+1$ and it is $0\pmod p.$ For $p=3$ the answer is $3$ so assume $p>3.$ Then $p\mid x^2+x+1$ implies $x$ has order $3\pmod p,$ so $p\equiv 1\pmod 3$ and $x=g^{\frac{p-1}3},g^{\frac{2(p-1)}3}$ for two solutions. Thus this sum is $-1\pmod p$ for $p\equiv 2\pmod 3$ and $-3\pmod p$ for $p\equiv 1\pmod 3.$

Thus the final answer is $0$ for $p=3,$ and $1$ for $p\equiv 1\pmod 3,$ and $-1$ for $p\equiv 2\pmod 3.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

119 posts

watery

#12 h Feb 10, 2025, 8:43 PM

Y by

As a remark, the answer is actually given by the integral $f(p) = \frac{1}{2\pi}\int_0^{2\pi}\left(1+2\cos{t}\right)^{p-1} \, \mathrm{d}t.$ I'm not sure if this is readily computable by elementary methods, though.

This post has been edited 1 time. Last edited by watery, Feb 10, 2025, 11:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6 posts

#13 h Today at 11:22 AM

Y by

watery wrote:

As a remark, the answer is actually given by the integral $f(p) = \frac{1}{2\pi}\int_0^{2\pi}\left(1+2\cos{t}\right)^{p-1} \, \mathrm{d}t.$ I'm not sure if this is readily computable by elementary methods, though.

please explain sir how you got it

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a