Random Fun Problems

BIMO Junior Proposal

Let $k$ be a fixed positive integer and $f$ be a polynomial with integer coefficients such that $f(x) \neq 0$ and $f(x) \mid f(x + k)$ for all $x \in \mathbb{Z}$. Prove that $f$ is constant.

Click for Solution Assume $f(x) = a_nx^n + \cdots + a_0$ is nonconstant. Then there exists some $N \in \mathbb{R}$ such that $f|_{x\geq N}$ is injective. However, $\lim_{x\rightarrow \infty} \frac{f(x+h)}{f(x)}= \frac{a_n}{a_n} = 1$, and since $f(x) \mid f(x + k)$ for all integers $x$, there exists some $M\in \mathbb{R}$ such that $f(x+h)=f(x)$ for all integers $x\geq M$. This contradicts with injectivity.


Electric Field Above Uniformly Charged Square Plate

(Source: Introduction to Electrodynamics by Griffiths, Chapter 2) Find the electric field at a height $z$ above the center of a square sheet (side $s$) carrying a uniform surface charge $\sigma$.

Click for Solution Answer: $\frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]$
Proof:

$$\begin{aligned}\int_0^\frac{\pi}{4}\frac{d\theta}{\sqrt{k^2+\sec^2\theta}} &= \int_0^\frac{\pi}{4}\frac{\cos\theta \ d\theta}{\sqrt{k^2\cos^2\theta+1}}\\ &= \int_0^{1/\sqrt{2}}\frac{du}{\sqrt{k^2(1-u^2)+1}}\\ &= \frac{1}{k}\int_0^{1/\sqrt{2}}\frac{du}{\sqrt{(1+k^{-2} - u^2)}}\\ &= \frac{1}{k}\arcsin\left(\frac{1/\sqrt{2}}{\sqrt{1+k^{-2}}}\right)\\ &= \frac{1}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ Let $\triangle$ be the triangle with vertices $(0,0),(1,0),(1,1)$. $$\begin{aligned}f(k) & = \int_{-1}^1 \int_{-1}^1 \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\iint_{\triangle} \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\int_0^{\frac{\pi}{4}} \int_{0}^{\sec\theta} \frac{r \ dr \ d\theta}{(k^2+r^2)^{3/2}}\\ &= 4\int_0^{\frac{\pi}{4}} \left[\int_{0}^{\sec\theta} \frac{d(k^2+r^2)}{(k^2+r^2)^{3/2}}\right] d\theta\\ &= 8\int_0^{\frac{\pi}{4}} \left[\frac{1}{k} - \frac{1}{\sqrt{k^2+\sec^2\theta}}\right] d\theta\\ &= \frac{2\pi}{k} - \frac{8}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ At a height $z$ above the center, $$\begin{aligned}V(z) &= \frac{1}{4\pi \varepsilon_0} \int_{S} \frac{dq}{r} = \frac{\sigma}{4\pi \varepsilon_0} \int_S \frac{dx \ dy}{\sqrt{z^2+x^2+y^2}}\\ E(z) = - \frac{\partial V}{\partial z} &= \frac{\sigma}{4\pi \varepsilon_0} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{z\ dx \ dy}{(z^2+x^2+y^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{d(2x/s) \ d(2y/s)}{((2z/s)^2+(2x/s)^2+(2y/s)^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} f(2z/s)\\ &= \frac{\sigma}{2\varepsilon_0}\left[1 - \frac{4}{\pi}\arctan\left(\frac{z}{\sqrt{z^2+s^2/2}}\right)\right]\\ &= \frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]\end{aligned}$$


General Solution for Linear Recursion

Suppose $a_n = c_{k-1}a_{n-1}+c_{k-2}a_{n-2}+\cdots + c_{0}a_{n-k}$ is a recursive relation of $a_i$ with constants $c_1,\cdots,c_{k-1}$. We define the characteristic polynomial of this relation as $f(x) = x^k - c_{k-1}x^{k-1}- c_{k-2}x^{k-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $a_n$ is

$a_n = \sum_{i} (C_{i,0} + nC_{i,1} + \cdots + n^{m_i-1} C_{i,m_i-1}) \lambda _i^n$.

where $C_{i,j}$ are all constants determined by the initial terms of the recursion.

Click for Proof Let $\vec{v_n}=[a_n,a_{n-1},\cdots,a_{n-k+1}]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{k-1} & 1 & 0 & \cdots & 0\\ c_{k-2} & 0 & 1 & \cdots & 0\\ c_{k-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v_n}M = \vec{v_{n+1}}$ and thus $\vec{v_n} = \vec{v_0} M^n$. It is easy to verify that $\text{det}(xI-M)=f(x)$ via induction by expanding the last row. Write $M=P^{-1} J P$ in Jordan Form. Hence $\vec{v_n} = \vec{v_0}P^{-1}J^n P$. Recall that $J^n$ is made up of $n$-th powers of Jordan blocks, whose entries are all in the form $\lambda _i^{n-j} \binom{n}{j}$ etc. $\binom{n}{j}$ is just a polynomial in $n$. Expanded out, the first entry $a_n$ of $\vec{v_n}$ definitely has the form as stated in the problem.


General Solution for Homogeneous Differential Equation

Suppose $y^{(n)} = c_{n-1}y^{(n-1)} + c_{n-2}y^{(n-2)} + \cdots + c_0 y$ is an ordinary differential equation of $y(t)$ with constants $c_1,\cdots,c_{n-1}$. We define the characteristic polynomial of this ODE as $f(x) = x^k - c_{n-1}x^{n-1}- c_{n-2}x^{n-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $y$ is

$y(t) = \sum_{i} (C_{i,0} + tC_{i,1} + \cdots + t^{m_i-1} C_{i,m_i-1}) e^{\lambda _it}$.

where $C_{i,j}$ are all constants.

Click for Proof We proceed like the previous problem. Let $\vec{v}=[y^{(n-1)},y^{(n-2)},\cdots,y]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{n-1} & 1 & 0 & \cdots & 0\\ c_{n-2} & 0 & 1 & \cdots & 0\\ c_{n-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v}M = \frac{d\vec{v}}{dt}$. Using the useful property of matrix exponentials, $\vec{v}=\vec{v_0}e^{tM}$ for some constant $\vec{v_0}$. Write $M$ as the Jordan form and proceed as the previous problem.


Burnside's Lemma (The Lemma that is not Burnside's)

Let $G$ be any permutation group of $N=\\{1,\cdots,n\\}$. Let $f: N\rightarrow \\{1,\cdots,m\\}$ be a colouring of $N$ with $m$ colours. Two colourings $f_1$ and $f_2$ are said to be equivalent if $f_1=f_2 \circ g$ for some $g\in G$. The number of equivalence classes is $ \frac{1}{|G|}\sum_{g\in G} m^{C(g)}$ where $C(g)$ is the number of cycles in the cyclic decomposition of $g$.

Click for Proof Let $G$ act on the set $S= {f_i}$ of colourings by the rule $g(f) = f \circ g$. The number of colourings fixed by an element $g\in G$ is exactly $m^{C(g)}$ because for such colourings, every element of ${1,\cdots,n}$ situated in the same cycle of $g$ must have the same colour and elements situated in different cycles can freely have different colours. Therefore, using double counting, $\sum_{g\in G} m^{C(g)} = \sum_{f \in S} |\text{Stab}(f)|$. By the Orbit-Stabiliser theorem, $|\text{Stab}(f)| = \frac{|G|}{|O_f|} $ where $O_f$ is the orbit of $f$. In conclusion, the number of orbits in total is $\sum_{f\in S} \frac{1}{|O_f|} = \sum_{f\in S} \frac{|\text{Stab}(f)|}{|G|} = \frac{1}{|G|} \sum_{g\in G} m^{C(g)}$.

Masalah Menarik

Masalah Cadangan BIMO Junior

Andaikan $k$ ialah suatu integer positif dan $f$ ialah suatu polynomial dengan pekali-pekali integer sehinggakan $f(x) \neq 0$ dan $f(x) \mid f(x + k)$ bagi semua $x \in \mathbb{Z}$. Buktikan bahawa $f$ adalah malar.

Click for Solution Assume $f(x) = a_nx^n + \cdots + a_0$ is nonconstant. Then there exists some $N \in \mathbb{R}$ such that $f|_{x\geq N}$ is injective. However, $\lim_{x\rightarrow \infty} \frac{f(x+h)}{f(x)}= \frac{a_n}{a_n} = 1$, and since $f(x) \mid f(x + k)$ for all integers $x$, there exists some $M\in \mathbb{R}$ such that $f(x+h)=f(x)$ for all integers $x\geq M$. This contradicts with injectivity.


Electric Field Above Uniformly Charged Square Plate

(Source: Introduction to Electrodynamics by Griffiths, Chapter 2) Find the electric field at a height $z$ above the center of a square sheet (side $s$) carrying a uniform surface charge $\sigma$.

Click for Solution Answer: $\frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]$
Proof:

$$\begin{aligned}\int_0^\frac{\pi}{4}\frac{d\theta}{\sqrt{k^2+\sec^2\theta}} &= \int_0^\frac{\pi}{4}\frac{\cos\theta \ d\theta}{\sqrt{k^2\cos^2\theta+1}}\\ &= \int_0^{1/\sqrt{2}}\frac{du}{\sqrt{k^2(1-u^2)+1}}\\ &= \frac{1}{k}\int_0^{1/\sqrt{2}}\frac{du}{\sqrt{(1+k^{-2} - u^2)}}\\ &= \frac{1}{k}\arcsin\left(\frac{1/\sqrt{2}}{\sqrt{1+k^{-2}}}\right)\\ &= \frac{1}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ Let $\triangle$ be the triangle with vertices $(0,0),(1,0),(1,1)$. $$\begin{aligned}f(k) & = \int_{-1}^1 \int_{-1}^1 \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\iint_{\triangle} \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\int_0^{\frac{\pi}{4}} \int_{0}^{\sec\theta} \frac{r \ dr \ d\theta}{(k^2+r^2)^{3/2}}\\ &= 4\int_0^{\frac{\pi}{4}} \left[\int_{0}^{\sec\theta} \frac{d(k^2+r^2)}{(k^2+r^2)^{3/2}}\right] d\theta\\ &= 8\int_0^{\frac{\pi}{4}} \left[\frac{1}{k} - \frac{1}{\sqrt{k^2+\sec^2\theta}}\right] d\theta\\ &= \frac{2\pi}{k} - \frac{8}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ Find the electric field at a height $z$ above the center of a square sheet (side $s$) carrying a uniform surface charge $\sigma$. $$\begin{aligned}V(z) &= \frac{1}{4\pi \varepsilon_0} \int_{S} \frac{dq}{r} = \frac{\sigma}{4\pi \varepsilon_0} \int_S \frac{dx \ dy}{\sqrt{z^2+x^2+y^2}}\\ E(z) = - \frac{\partial V}{\partial z} &= \frac{\sigma}{4\pi \varepsilon_0} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{z\ dx \ dy}{(z^2+x^2+y^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{d(2x/s) \ d(2y/s)}{((2z/s)^2+(2x/s)^2+(2y/s)^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} f(2z/s)\\ &= \frac{\sigma}{2\varepsilon_0}\left[1 - \frac{4}{\pi}\arctan\left(\frac{z}{\sqrt{z^2+s^2/2}}\right)\right]\\ &= \frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]\end{aligned}$$


General Solution for Linear Recursion

Suppose $a_n = c_{k-1}a_{n-1}+c_{k-2}a_{n-2}+\cdots + c_{0}a_{n-k}$ is a recursive relation of $a_i$ with constants $c_1,\cdots,c_{k-1}$. We define the characteristic polynomial of this relation as $f(x) = x^k - c_{k-1}x^{k-1}- c_{k-2}x^{k-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $a_n$ is

$a_n = \sum_{i} (C_{i,0} + nC_{i,1} + \cdots + n^{m_i-1} C_{i,m_i-1}) \lambda _i^n$.

where $C_{i,j}$ are all constants determined by the initial terms of the recursion.

Click for Proof Let $\vec{v_n}=[a_n,a_{n-1},\cdots,a_{n-k+1}]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{k-1} & 1 & 0 & \cdots & 0\\ c_{k-2} & 0 & 1 & \cdots & 0\\ c_{k-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v_n}M = \vec{v_{n+1}}$ and thus $\vec{v_n} = \vec{v_0} M^n$. It is easy to verify that $\text{det}(xI-M)=f(x)$ via induction by expanding the last row. Write $M=P^{-1} J P$ in Jordan Form. Hence $\vec{v_n} = \vec{v_0}P^{-1}J^n P$. Recall that $J^n$ is made up of $n$-th powers of Jordan blocks, whose entries are all in the form $\lambda _i^{n-j} \binom{n}{j}$ etc. $\binom{n}{j}$ is just a polynomial in $n$. Expanded out, the first entry $a_n$ of $\vec{v_n}$ definitely has the form as stated in the problem.


General Solution for Homogeneous Differential Equation

Suppose $y^{(n)} = c_{n-1}y^{(n-1)} + c_{n-2}y^{(n-2)} + \cdots + c_0 y$ is an ordinary differential equation of $y(t)$ with constants $c_1,\cdots,c_{n-1}$. We define the characteristic polynomial of this ODE as $f(x) = x^k - c_{n-1}x^{n-1}- c_{n-2}x^{n-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $y$ is

$y(t) = \sum_{i} (C_{i,0} + tC_{i,1} + \cdots + t^{m_i-1} C_{i,m_i-1}) e^{\lambda _it}$.

where $C_{i,j}$ are all constants.

Click for Proof We proceed like the previous problem. Let $\vec{v}=[y^{(n-1)},y^{(n-2)},\cdots,y]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{n-1} & 1 & 0 & \cdots & 0\\ c_{n-2} & 0 & 1 & \cdots & 0\\ c_{n-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v}M = \frac{d\vec{v}}{dt}$. Using the useful property of matrix exponentials, $\vec{v}=\vec{v_0}e^{tM}$ for some constant $\vec{v_0}$. Write $M$ as the Jordan form and proceed as the previous problem.


Burnside's Lemma (The Lemma that is not Burnside's)

Let $G$ be any permutation group of $N=\\{1,\cdots,n\\}$. Let $f: N\rightarrow \\{1,\cdots,m\\}$ be a colouring of $N$ with $m$ colours. Two colourings $f_1$ and $f_2$ are said to be equivalent if $f_1=f_2 \circ g$ for some $g\in G$. The number of equivalence classes is $ \frac{1}{|G|}\sum_{g\in G} m^{C(g)}$ where $C(g)$ is the number of cycles in the cyclic decomposition of $g$.

Click for Proof Let $G$ act on the set $S= {f_i}$ of colourings by the rule $g(f) = f \circ g$. The number of colourings fixed by an element $g\in G$ is exactly $m^{C(g)}$ because for such colourings, every element of ${1,\cdots,n}$ situated in the same cycle of $g$ must have the same colour and elements situated in different cycles can freely have different colours. Therefore, using double counting, $\sum_{g\in G} m^{C(g)} = \sum_{f \in S} |\text{Stab}(f)|$. By the Orbit-Stabiliser theorem, $|\text{Stab}(f)| = \frac{|G|}{|O_f|} $ where $O_f$ is the orbit of $f$. In conclusion, the number of orbits in total is $\sum_{f\in S} \frac{1}{|O_f|} = \sum_{f\in S} \frac{|\text{Stab}(f)|}{|G|} = \frac{1}{|G|} \sum_{g\in G} m^{C(g)}$.

有趣的题目

中级BIMO自写题目

已知 $k$ 为正整数及$f$为正数系数多项式,使得对于所有 $x \in \mathbb{Z}$,有 $f(x) \neq 0$ 和 $f(x) \mid f(x + k)$。证明 $f$ 为常数多项式。

点击显示解法 假设 $f(x) = a_nx^n + \cdots + a_0$ 不是常数,则存在正整数 $N$ 使得 $f|_{x\geq N}$ 为单射函数。但,$\lim_{x\rightarrow \infty} \frac{f(x+h)}{f(x)}= \frac{a_n}{a_n} = 1$, 且对所有整数 $x$ 有 $f(x) \mid f(x + k)$,所以必定存在 $M\in \mathbb{R}$ 使得对于所有整数$x\geq M$ 有 $f(x+h)=f(x)$。这与 $f$ 的单射性质矛盾。


均匀表面电荷正方形上的电场

(Source: Introduction to Electrodynamics by Griffiths, 第 2 章节) 计算一带有均匀表面电荷 $\sigma$,边长为 $s$ 的正方形薄片中心上方高度为 $z$ 处的电场强度。

点击显示解法 Answer: $\frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]$
Proof:

$$\begin{aligned}\int_0^\frac{\pi}{4}\frac{d\theta}{\sqrt{k^2+\sec^2\theta}} &= \int_0^\frac{\pi}{4}\frac{\cos\theta \ d\theta}{\sqrt{k^2\cos^2\theta+1}}\\ &= \int_0^{1/\sqrt{2}}\frac{du}{\sqrt{k^2(1-u^2)+1}}\\ &= \frac{1}{k}\int_0^{1/\sqrt{2}}\frac{du}{\sqrt{(1+k^{-2} - u^2)}}\\ &= \frac{1}{k}\arcsin\left(\frac{1/\sqrt{2}}{\sqrt{1+k^{-2}}}\right)\\ &= \frac{1}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ 将顶点为 $(0,0),(1,0),(1,1)$ 的三角形写作 $\triangle$。 $$\begin{aligned}f(k) & = \int_{-1}^1 \int_{-1}^1 \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\iint_{\triangle} \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\int_0^{\frac{\pi}{4}} \int_{0}^{\sec\theta} \frac{r \ dr \ d\theta}{(k^2+r^2)^{3/2}}\\ &= 4\int_0^{\frac{\pi}{4}} \left[\int_{0}^{\sec\theta} \frac{d(k^2+r^2)}{(k^2+r^2)^{3/2}}\right] d\theta\\ &= 8\int_0^{\frac{\pi}{4}} \left[\frac{1}{k} - \frac{1}{\sqrt{k^2+\sec^2\theta}}\right] d\theta\\ &= \frac{2\pi}{k} - \frac{8}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ 在高度 $z$, $$\begin{aligned}V(z) &= \frac{1}{4\pi \varepsilon_0} \int_{S} \frac{dq}{r} = \frac{\sigma}{4\pi \varepsilon_0} \int_S \frac{dx \ dy}{\sqrt{z^2+x^2+y^2}}\\ E(z) = - \frac{\partial V}{\partial z} &= \frac{\sigma}{4\pi \varepsilon_0} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{z\ dx \ dy}{(z^2+x^2+y^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{d(2x/s) \ d(2y/s)}{((2z/s)^2+(2x/s)^2+(2y/s)^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} f(2z/s)\\ &= \frac{\sigma}{2\varepsilon_0}\left[1 - \frac{4}{\pi}\arctan\left(\frac{z}{\sqrt{z^2+s^2/2}}\right)\right]\\ &= \frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]\end{aligned}$$


General Solution for Linear Recursion

Suppose $a_n = c_{k-1}a_{n-1}+c_{k-2}a_{n-2}+\cdots + c_{0}a_{n-k}$ is a recursive relation of $a_i$ with constants $c_1,\cdots,c_{k-1}$. We define the characteristic polynomial of this relation as $f(x) = x^k - c_{k-1}x^{k-1}- c_{k-2}x^{k-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $a_n$ is

$a_n = \sum_{i} (C_{i,0} + nC_{i,1} + \cdots + n^{m_i-1} C_{i,m_i-1}) \lambda _i^n$.

where $C_{i,j}$ are all constants determined by the initial terms of the recursion.

Click for Proof Let $\vec{v_n}=[a_n,a_{n-1},\cdots,a_{n-k+1}]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{k-1} & 1 & 0 & \cdots & 0\\ c_{k-2} & 0 & 1 & \cdots & 0\\ c_{k-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v_n}M = \vec{v_{n+1}}$ and thus $\vec{v_n} = \vec{v_0} M^n$. It is easy to verify that $\text{det}(xI-M)=f(x)$ via induction by expanding the last row. Write $M=P^{-1} J P$ in Jordan Form. Hence $\vec{v_n} = \vec{v_0}P^{-1}J^n P$. Recall that $J^n$ is made up of $n$-th powers of Jordan blocks, whose entries are all in the form $\lambda _i^{n-j} \binom{n}{j}$ etc. $\binom{n}{j}$ is just a polynomial in $n$. Expanded out, the first entry $a_n$ of $\vec{v_n}$ definitely has the form as stated in the problem.


General Solution for Homogeneous Differential Equation

Suppose $y^{(n)} = c_{n-1}y^{(n-1)} + c_{n-2}y^{(n-2)} + \cdots + c_0 y$ is an ordinary differential equation of $y(t)$ with constants $c_1,\cdots,c_{n-1}$. We define the characteristic polynomial of this ODE as $f(x) = x^k - c_{n-1}x^{n-1}- c_{n-2}x^{n-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $y$ is

$y(t) = \sum_{i} (C_{i,0} + tC_{i,1} + \cdots + t^{m_i-1} C_{i,m_i-1}) e^{\lambda _it}$.

where $C_{i,j}$ are all constants.

Click for Proof We proceed like the previous problem. Let $\vec{v}=[y^{(n-1)},y^{(n-2)},\cdots,y]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{n-1} & 1 & 0 & \cdots & 0\\ c_{n-2} & 0 & 1 & \cdots & 0\\ c_{n-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v}M = \frac{d\vec{v}}{dt}$. Using the useful property of matrix exponentials, $\vec{v}=\vec{v_0}e^{tM}$ for some constant $\vec{v_0}$. Write $M$ as the Jordan form and proceed as the previous problem.


Burnside's Lemma (The Lemma that is not Burnside's)

Let $G$ be any permutation group of $N=\\{1,\cdots,n\\}$. Let $f: N\rightarrow \\{1,\cdots,m\\}$ be a colouring of $N$ with $m$ colours. Two colourings $f_1$ and $f_2$ are said to be equivalent if $f_1=f_2 \circ g$ for some $g\in G$. The number of equivalence classes is $ \frac{1}{|G|}\sum_{g\in G} m^{C(g)}$ where $C(g)$ is the number of cycles in the cyclic decomposition of $g$.

Click for Proof Let $G$ act on the set $S= {f_i}$ of colourings by the rule $g(f) = f \circ g$. The number of colourings fixed by an element $g\in G$ is exactly $m^{C(g)}$ because for such colourings, every element of ${1,\cdots,n}$ situated in the same cycle of $g$ must have the same colour and elements situated in different cycles can freely have different colours. Therefore, using double counting, $\sum_{g\in G} m^{C(g)} = \sum_{f \in S} |\text{Stab}(f)|$. By the Orbit-Stabiliser theorem, $|\text{Stab}(f)| = \frac{|G|}{|O_f|} $ where $O_f$ is the orbit of $f$. In conclusion, the number of orbits in total is $\sum_{f\in S} \frac{1}{|O_f|} = \sum_{f\in S} \frac{|\text{Stab}(f)|}{|G|} = \frac{1}{|G|} \sum_{g\in G} m^{C(g)}$.

得意嘅題目

中級BIMO自寫題目

已知 $k$ 為正整數及 $f$ 為正數係數多項式,使得對所有 $x \in \mathbb{Z}$,有 $f(x) \neq 0$ 和 $f(x) \mid f(x + k)$。證明 $f$ 為常數多項式。

撳掣睇答案 假設 $f(x) = a_nx^n + \cdots + a_0$ 不是常數,則存在正整數 $N$ 使得 $f|_{x\geq N}$ 為單射函數。但,$\lim_{x\rightarrow \infty} \frac{f(x+h)}{f(x)}= \frac{a_n}{a_n} = 1$, 且對所有整數 $x$ 有 $f(x) \mid f(x + k)$,所以必定存在 $Mqin \m $f(x+h)=f(x)$。這與 $f$ 的單射性質矛盾。


均勻表面電荷正方形上的電場

(Source: Introduction to Electrodynamics by Griffiths, 第 2 章節) 計算一具有均勻表面電荷 $\sigma$,邊長為 $s$ 的正方形薄片中心上方高度為 $z$ 處的電場強度。

撳掣睇答案 Answer: $\frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]$
Proof:

$$\begin{aligned}\int_0^\frac{\pi}{4}\frac{d\theta}{\sqrt{k^2+\sec^2\theta}} &= \int_0^\frac{\pi}{4}\frac{\cos\theta \ d\theta}{\sqrt{k^2\cos^2\theta+1}}\\ &= \int_0^{1/\sqrt{2}}\frac{du}{\sqrt{k^2(1-u^2)+1}}\\ &= \frac{1}{k}\int_0^{1/\sqrt{2}}\frac{du}{\sqrt{(1+k^{-2} - u^2)}}\\ &= \frac{1}{k}\arcsin\left(\frac{1/\sqrt{2}}{\sqrt{1+k^{-2}}}\right)\\ &= \frac{1}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ 將頂點為 $(0,0),(1,0),(1,1)$ 的三角形寫成 $\triangle$。 $$\begin{aligned}f(k) & = \int_{-1}^1 \int_{-1}^1 \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\iint_{\triangle} \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\int_0^{\frac{\pi}{4}} \int_{0}^{\sec\theta} \frac{r \ dr \ d\theta}{(k^2+r^2)^{3/2}}\\ &= 4\int_0^{\frac{\pi}{4}} \left[\int_{0}^{\sec\theta} \frac{d(k^2+r^2)}{(k^2+r^2)^{3/2}}\right] d\theta\\ &= 8\int_0^{\frac{\pi}{4}} \left[\frac{1}{k} - \frac{1}{\sqrt{k^2+\sec^2\theta}}\right] d\theta\\ &= \frac{2\pi}{k} - \frac{8}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ 在高度 $z$, $$\begin{aligned}V(z) &= \frac{1}{4\pi \varepsilon_0} \int_{S} \frac{dq}{r} = \frac{\sigma}{4\pi \varepsilon_0} \int_S \frac{dx \ dy}{\sqrt{z^2+x^2+y^2}}\\ E(z) = - \frac{\partial V}{\partial z} &= \frac{\sigma}{4\pi \varepsilon_0} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{z\ dx \ dy}{(z^2+x^2+y^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{d(2x/s) \ d(2y/s)}{((2z/s)^2+(2x/s)^2+(2y/s)^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} f(2z/s)\\ &= \frac{\sigma}{2\varepsilon_0}\left[1 - \frac{4}{\pi}\arctan\left(\frac{z}{\sqrt{z^2+s^2/2}}\right)\right]\\ &= \frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]\end{aligned}$$


General Solution for Linear Recursion

Suppose $a_n = c_{k-1}a_{n-1}+c_{k-2}a_{n-2}+\cdots + c_{0}a_{n-k}$ is a recursive relation of $a_i$ with constants $c_1,\cdots,c_{k-1}$. We define the characteristic polynomial of this relation as $f(x) = x^k - c_{k-1}x^{k-1}- c_{k-2}x^{k-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $a_n$ is

$a_n = \sum_{i} (C_{i,0} + nC_{i,1} + \cdots + n^{m_i-1} C_{i,m_i-1}) \lambda _i^n$.

where $C_{i,j}$ are all constants determined by the initial terms of the recursion.

Click for Proof Let $\vec{v_n}=[a_n,a_{n-1},\cdots,a_{n-k+1}]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{k-1} & 1 & 0 & \cdots & 0\\ c_{k-2} & 0 & 1 & \cdots & 0\\ c_{k-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v_n}M = \vec{v_{n+1}}$ and thus $\vec{v_n} = \vec{v_0} M^n$. It is easy to verify that $\text{det}(xI-M)=f(x)$ via induction by expanding the last row. Write $M=P^{-1} J P$ in Jordan Form. Hence $\vec{v_n} = \vec{v_0}P^{-1}J^n P$. Recall that $J^n$ is made up of $n$-th powers of Jordan blocks, whose entries are all in the form $\lambda _i^{n-j} \binom{n}{j}$ etc. $\binom{n}{j}$ is just a polynomial in $n$. Expanded out, the first entry $a_n$ of $\vec{v_n}$ definitely has the form as stated in the problem.


General Solution for Homogeneous Differential Equation

Suppose $y^{(n)} = c_{n-1}y^{(n-1)} + c_{n-2}y^{(n-2)} + \cdots + c_0 y$ is an ordinary differential equation of $y(t)$ with constants $c_1,\cdots,c_{n-1}$. We define the characteristic polynomial of this ODE as $f(x) = x^k - c_{n-1}x^{n-1}- c_{n-2}x^{n-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $y$ is

$y(t) = \sum_{i} (C_{i,0} + tC_{i,1} + \cdots + t^{m_i-1} C_{i,m_i-1}) e^{\lambda _it}$.

where $C_{i,j}$ are all constants.

Click for Proof We proceed like the previous problem. Let $\vec{v}=[y^{(n-1)},y^{(n-2)},\cdots,y]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{n-1} & 1 & 0 & \cdots & 0\\ c_{n-2} & 0 & 1 & \cdots & 0\\ c_{n-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v}M = \frac{d\vec{v}}{dt}$. Using the useful property of matrix exponentials, $\vec{v}=\vec{v_0}e^{tM}$ for some constant $\vec{v_0}$. Write $M$ as the Jordan form and proceed as the previous problem.


Burnside's Lemma (The Lemma that is not Burnside's)

Let $G$ be any permutation group of $N=\\{1,\cdots,n\\}$. Let $f: N\rightarrow \\{1,\cdots,m\\}$ be a colouring of $N$ with $m$ colours. Two colourings $f_1$ and $f_2$ are said to be equivalent if $f_1=f_2 \circ g$ for some $g\in G$. The number of equivalence classes is $ \frac{1}{|G|}\sum_{g\in G} m^{C(g)}$ where $C(g)$ is the number of cycles in the cyclic decomposition of $g$.

Click for Proof Let $G$ act on the set $S= {f_i}$ of colourings by the rule $g(f) = f \circ g$. The number of colourings fixed by an element $g\in G$ is exactly $m^{C(g)}$ because for such colourings, every element of ${1,\cdots,n}$ situated in the same cycle of $g$ must have the same colour and elements situated in different cycles can freely have different colours. Therefore, using double counting, $\sum_{g\in G} m^{C(g)} = \sum_{f \in S} |\text{Stab}(f)|$. By the Orbit-Stabiliser theorem, $|\text{Stab}(f)| = \frac{|G|}{|O_f|} $ where $O_f$ is the orbit of $f$. In conclusion, the number of orbits in total is $\sum_{f\in S} \frac{1}{|O_f|} = \sum_{f\in S} \frac{|\text{Stab}(f)|}{|G|} = \frac{1}{|G|} \sum_{g\in G} m^{C(g)}$.

Problèmes Intéressants

Proposition BIMO Junior

Soit $k$ un entier positif fixe et $f$ un polynôme à coefficients entiers tels que $f(x) \neq 0$ et $f(x) \mid f(x + k)$ pour tout $x \in \mathbb{Z}$. Démontrer que $f$ est constante.

Click for Solution Assume $f(x) = a_nx^n + \cdots + a_0$ is nonconstant. Then there exists some $N \in \mathbb{R}$ such that $f|_{x\geq N}$ is injective. However, $\lim_{x\rightarrow \infty} \frac{f(x+h)}{f(x)}= \frac{a_n}{a_n} = 1$, and since $f(x) \mid f(x + k)$ for all integers $x$, there exists some $M\in \mathbb{R}$ such that $f(x+h)=f(x)$ for all integers $x\geq M$. This contradicts with injectivity.


Electric Field Above Uniformly Charged Square Plate

(Source: Introduction to Electrodynamics by Griffiths, Chapter 2) Find the electric field at a height $z$ above the center of a square sheet (side $s$) carrying a uniform surface charge $\sigma$.

Click for Solution Answer: $\frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]$
Proof:

$$\begin{aligned}\int_0^\frac{\pi}{4}\frac{d\theta}{\sqrt{k^2+\sec^2\theta}} &= \int_0^\frac{\pi}{4}\frac{\cos\theta \ d\theta}{\sqrt{k^2\cos^2\theta+1}}\\ &= \int_0^{1/\sqrt{2}}\frac{du}{\sqrt{k^2(1-u^2)+1}}\\ &= \frac{1}{k}\int_0^{1/\sqrt{2}}\frac{du}{\sqrt{(1+k^{-2} - u^2)}}\\ &= \frac{1}{k}\arcsin\left(\frac{1/\sqrt{2}}{\sqrt{1+k^{-2}}}\right)\\ &= \frac{1}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ Let $\triangle$ be the triangle with vertices $(0,0),(1,0),(1,1)$. $$\begin{aligned}f(k) & = \int_{-1}^1 \int_{-1}^1 \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\iint_{\triangle} \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\int_0^{\frac{\pi}{4}} \int_{0}^{\sec\theta} \frac{r \ dr \ d\theta}{(k^2+r^2)^{3/2}}\\ &= 4\int_0^{\frac{\pi}{4}} \left[\int_{0}^{\sec\theta} \frac{d(k^2+r^2)}{(k^2+r^2)^{3/2}}\right] d\theta\\ &= 8\int_0^{\frac{\pi}{4}} \left[\frac{1}{k} - \frac{1}{\sqrt{k^2+\sec^2\theta}}\right] d\theta\\ &= \frac{2\pi}{k} - \frac{8}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ Find the electric field at a height $z$ above the center of a square sheet (side $s$) carrying a uniform surface charge $\sigma$. $$\begin{aligned}V(z) &= \frac{1}{4\pi \varepsilon_0} \int_{S} \frac{dq}{r} = \frac{\sigma}{4\pi \varepsilon_0} \int_S \frac{dx \ dy}{\sqrt{z^2+x^2+y^2}}\\ E(z) = - \frac{\partial V}{\partial z} &= \frac{\sigma}{4\pi \varepsilon_0} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{z\ dx \ dy}{(z^2+x^2+y^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{d(2x/s) \ d(2y/s)}{((2z/s)^2+(2x/s)^2+(2y/s)^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} f(2z/s)\\ &= \frac{\sigma}{2\varepsilon_0}\left[1 - \frac{4}{\pi}\arctan\left(\frac{z}{\sqrt{z^2+s^2/2}}\right)\right]\\ &= \frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]\end{aligned}$$


General Solution for Linear Recursion

Suppose $a_n = c_{k-1}a_{n-1}+c_{k-2}a_{n-2}+\cdots + c_{0}a_{n-k}$ is a recursive relation of $a_i$ with constants $c_1,\cdots,c_{k-1}$. We define the characteristic polynomial of this relation as $f(x) = x^k - c_{k-1}x^{k-1}- c_{k-2}x^{k-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $a_n$ is

$a_n = \sum_{i} (C_{i,0} + nC_{i,1} + \cdots + n^{m_i-1} C_{i,m_i-1}) \lambda _i^n$.

where $C_{i,j}$ are all constants determined by the initial terms of the recursion.

Click for Proof Let $\vec{v_n}=[a_n,a_{n-1},\cdots,a_{n-k+1}]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{k-1} & 1 & 0 & \cdots & 0\\ c_{k-2} & 0 & 1 & \cdots & 0\\ c_{k-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v_n}M = \vec{v_{n+1}}$ and thus $\vec{v_n} = \vec{v_0} M^n$. It is easy to verify that $\text{det}(xI-M)=f(x)$ via induction by expanding the last row. Write $M=P^{-1} J P$ in Jordan Form. Hence $\vec{v_n} = \vec{v_0}P^{-1}J^n P$. Recall that $J^n$ is made up of $n$-th powers of Jordan blocks, whose entries are all in the form $\lambda _i^{n-j} \binom{n}{j}$ etc. $\binom{n}{j}$ is just a polynomial in $n$. Expanded out, the first entry $a_n$ of $\vec{v_n}$ definitely has the form as stated in the problem.


General Solution for Homogeneous Differential Equation

Suppose $y^{(n)} = c_{n-1}y^{(n-1)} + c_{n-2}y^{(n-2)} + \cdots + c_0 y$ is an ordinary differential equation of $y(t)$ with constants $c_1,\cdots,c_{n-1}$. We define the characteristic polynomial of this ODE as $f(x) = x^k - c_{n-1}x^{n-1}- c_{n-2}x^{n-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $y$ is

$y(t) = \sum_{i} (C_{i,0} + tC_{i,1} + \cdots + t^{m_i-1} C_{i,m_i-1}) e^{\lambda _it}$.

where $C_{i,j}$ are all constants.

Click for Proof We proceed like the previous problem. Let $\vec{v}=[y^{(n-1)},y^{(n-2)},\cdots,y]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{n-1} & 1 & 0 & \cdots & 0\\ c_{n-2} & 0 & 1 & \cdots & 0\\ c_{n-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v}M = \frac{d\vec{v}}{dt}$. Using the useful property of matrix exponentials, $\vec{v}=\vec{v_0}e^{tM}$ for some constant $\vec{v_0}$. Write $M$ as the Jordan form and proceed as the previous problem.


Burnside's Lemma (The Lemma that is not Burnside's)

Let $G$ be any permutation group of $N=\\{1,\cdots,n\\}$. Let $f: N\rightarrow \\{1,\cdots,m\\}$ be a colouring of $N$ with $m$ colours. Two colourings $f_1$ and $f_2$ are said to be equivalent if $f_1=f_2 \circ g$ for some $g\in G$. The number of equivalence classes is $ \frac{1}{|G|}\sum_{g\in G} m^{C(g)}$ where $C(g)$ is the number of cycles in the cyclic decomposition of $g$.

Click for Proof Let $G$ act on the set $S= {f_i}$ of colourings by the rule $g(f) = f \circ g$. The number of colourings fixed by an element $g\in G$ is exactly $m^{C(g)}$ because for such colourings, every element of ${1,\cdots,n}$ situated in the same cycle of $g$ must have the same colour and elements situated in different cycles can freely have different colours. Therefore, using double counting, $\sum_{g\in G} m^{C(g)} = \sum_{f \in S} |\text{Stab}(f)|$. By the Orbit-Stabiliser theorem, $|\text{Stab}(f)| = \frac{|G|}{|O_f|} $ where $O_f$ is the orbit of $f$. In conclusion, the number of orbits in total is $\sum_{f\in S} \frac{1}{|O_f|} = \sum_{f\in S} \frac{|\text{Stab}(f)|}{|G|} = \frac{1}{|G|} \sum_{g\in G} m^{C(g)}$.

おもしろい問題

中段BIMOの自分の問題

$k$ は固定の正の整数であるし、$f$ を整数係数の多項式であるし、任意の $x \in \mathbb{Z}$ に対して $f(x) \neq 0$ と $f(x) \mid f(x + k)$とする。$f$ が定数であることを示せ。

Click for Solution Assume $f(x) = a_nx^n + \cdots + a_0$ is nonconstant. Then there exists some $N \in \mathbb{R}$ such that $f|_{x\geq N}$ is injective. However, $\lim_{x\rightarrow \infty} \frac{f(x+h)}{f(x)}= \frac{a_n}{a_n} = 1$, and since $f(x) \mid f(x + k)$ for all integers $x$, there exists some $M\in \mathbb{R}$ such that $f(x+h)=f(x)$ for all integers $x\geq M$. This contradicts with injectivity.


Electric Field Above Uniformly Charged Square Plate

(Source: Introduction to Electrodynamics by Griffiths, Chapter 2) Find the electric field at a height $z$ above the center of a square sheet (side $s$) carrying a uniform surface charge $\sigma$.

Click for Solution Answer: $\frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]$
Proof:

$$\begin{aligned}\int_0^\frac{\pi}{4}\frac{d\theta}{\sqrt{k^2+\sec^2\theta}} &= \int_0^\frac{\pi}{4}\frac{\cos\theta \ d\theta}{\sqrt{k^2\cos^2\theta+1}}\\ &= \int_0^{1/\sqrt{2}}\frac{du}{\sqrt{k^2(1-u^2)+1}}\\ &= \frac{1}{k}\int_0^{1/\sqrt{2}}\frac{du}{\sqrt{(1+k^{-2} - u^2)}}\\ &= \frac{1}{k}\arcsin\left(\frac{1/\sqrt{2}}{\sqrt{1+k^{-2}}}\right)\\ &= \frac{1}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ Let $\triangle$ be the triangle with vertices $(0,0),(1,0),(1,1)$. $$\begin{aligned}f(k) & = \int_{-1}^1 \int_{-1}^1 \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\iint_{\triangle} \frac{dx \ dy}{(k^2+x^2+y^2)^{3/2}}\\ &= 8\int_0^{\frac{\pi}{4}} \int_{0}^{\sec\theta} \frac{r \ dr \ d\theta}{(k^2+r^2)^{3/2}}\\ &= 4\int_0^{\frac{\pi}{4}} \left[\int_{0}^{\sec\theta} \frac{d(k^2+r^2)}{(k^2+r^2)^{3/2}}\right] d\theta\\ &= 8\int_0^{\frac{\pi}{4}} \left[\frac{1}{k} - \frac{1}{\sqrt{k^2+\sec^2\theta}}\right] d\theta\\ &= \frac{2\pi}{k} - \frac{8}{k}\arctan\left(\frac{k}{\sqrt{k^2+2}}\right)\end{aligned}$$ Find the electric field at a height $z$ above the center of a square sheet (side $s$) carrying a uniform surface charge $\sigma$. $$\begin{aligned}V(z) &= \frac{1}{4\pi \varepsilon_0} \int_{S} \frac{dq}{r} = \frac{\sigma}{4\pi \varepsilon_0} \int_S \frac{dx \ dy}{\sqrt{z^2+x^2+y^2}}\\ E(z) = - \frac{\partial V}{\partial z} &= \frac{\sigma}{4\pi \varepsilon_0} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{z\ dx \ dy}{(z^2+x^2+y^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} \int_{-s/2}^{s/2}\int_{-s/2}^{s/2} \frac{d(2x/s) \ d(2y/s)}{((2z/s)^2+(2x/s)^2+(2y/s)^2)^{3/2}}\\ &= \frac{\sigma z}{2\pi \varepsilon_0 s} f(2z/s)\\ &= \frac{\sigma}{2\varepsilon_0}\left[1 - \frac{4}{\pi}\arctan\left(\frac{z}{\sqrt{z^2+s^2/2}}\right)\right]\\ &= \frac{\sigma}{2\varepsilon_0}\left[\frac{4}{\pi}\arctan\left(\sqrt{1+s^2/2z^2}\right)-1\right]\end{aligned}$$


General Solution for Linear Recursion

Suppose $a_n = c_{k-1}a_{n-1}+c_{k-2}a_{n-2}+\cdots + c_{0}a_{n-k}$ is a recursive relation of $a_i$ with constants $c_1,\cdots,c_{k-1}$. We define the characteristic polynomial of this relation as $f(x) = x^k - c_{k-1}x^{k-1}- c_{k-2}x^{k-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $a_n$ is

$a_n = \sum_{i} (C_{i,0} + nC_{i,1} + \cdots + n^{m_i-1} C_{i,m_i-1}) \lambda _i^n$.

where $C_{i,j}$ are all constants determined by the initial terms of the recursion.

Click for Proof Let $\vec{v_n}=[a_n,a_{n-1},\cdots,a_{n-k+1}]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{k-1} & 1 & 0 & \cdots & 0\\ c_{k-2} & 0 & 1 & \cdots & 0\\ c_{k-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v_n}M = \vec{v_{n+1}}$ and thus $\vec{v_n} = \vec{v_0} M^n$. It is easy to verify that $\text{det}(xI-M)=f(x)$ via induction by expanding the last row. Write $M=P^{-1} J P$ in Jordan Form. Hence $\vec{v_n} = \vec{v_0}P^{-1}J^n P$. Recall that $J^n$ is made up of $n$-th powers of Jordan blocks, whose entries are all in the form $\lambda _i^{n-j} \binom{n}{j}$ etc. $\binom{n}{j}$ is just a polynomial in $n$. Expanded out, the first entry $a_n$ of $\vec{v_n}$ definitely has the form as stated in the problem.


General Solution for Homogeneous Differential Equation

Suppose $y^{(n)} = c_{n-1}y^{(n-1)} + c_{n-2}y^{(n-2)} + \cdots + c_0 y$ is an ordinary differential equation of $y(t)$ with constants $c_1,\cdots,c_{n-1}$. We define the characteristic polynomial of this ODE as $f(x) = x^k - c_{n-1}x^{n-1}- c_{n-2}x^{n-2} - \cdots - c_0$. If the factored form of $f(x)$ is $f(x) = \prod _i (x-\lambda _i)^{m_i}$ where $\lambda _i$ are distinct roots, then the general solution for $y$ is

$y(t) = \sum_{i} (C_{i,0} + tC_{i,1} + \cdots + t^{m_i-1} C_{i,m_i-1}) e^{\lambda _it}$.

where $C_{i,j}$ are all constants.

Click for Proof We proceed like the previous problem. Let $\vec{v}=[y^{(n-1)},y^{(n-2)},\cdots,y]$ for each $n\in \mathbb{Z}$. Note that if $M$ is the matrix

$\begin{bmatrix} c_{n-1} & 1 & 0 & \cdots & 0\\ c_{n-2} & 0 & 1 & \cdots & 0\\ c_{n-3} & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ c_0 & 0 & 0 & \cdots & 0 \end{bmatrix}$

then $\vec{v}M = \frac{d\vec{v}}{dt}$. Using the useful property of matrix exponentials, $\vec{v}=\vec{v_0}e^{tM}$ for some constant $\vec{v_0}$. Write $M$ as the Jordan form and proceed as the previous problem.


Burnside's Lemma (The Lemma that is not Burnside's)

Let $G$ be any permutation group of $N=\\{1,\cdots,n\\}$. Let $f: N\rightarrow \\{1,\cdots,m\\}$ be a colouring of $N$ with $m$ colours. Two colourings $f_1$ and $f_2$ are said to be equivalent if $f_1=f_2 \circ g$ for some $g\in G$. The number of equivalence classes is $ \frac{1}{|G|}\sum_{g\in G} m^{C(g)}$ where $C(g)$ is the number of cycles in the cyclic decomposition of $g$.

Click for Proof Let $G$ act on the set $S= {f_i}$ of colourings by the rule $g(f) = f \circ g$. The number of colourings fixed by an element $g\in G$ is exactly $m^{C(g)}$ because for such colourings, every element of ${1,\cdots,n}$ situated in the same cycle of $g$ must have the same colour and elements situated in different cycles can freely have different colours. Therefore, using double counting, $\sum_{g\in G} m^{C(g)} = \sum_{f \in S} |\text{Stab}(f)|$. By the Orbit-Stabiliser theorem, $|\text{Stab}(f)| = \frac{|G|}{|O_f|} $ where $O_f$ is the orbit of $f$. In conclusion, the number of orbits in total is $\sum_{f\in S} \frac{1}{|O_f|} = \sum_{f\in S} \frac{|\text{Stab}(f)|}{|G|} = \frac{1}{|G|} \sum_{g\in G} m^{C(g)}$.