TITLE: How to show that $E(X^k)=npE((Y + 1)^{k-1})$ where $X\sim\mathrm{Bin}(n,p)$ and $Y \sim \mathrm{Bin}(n-1,p)$.
QUESTION [0 upvotes]: Show that $$E(X^k)=npE((Y + 1)^{k-1})$$ where $X\sim\mathrm{Bin}(n,p)$ and $Y \sim\mathrm{Bin}(n-1,p)$.
I am looking for suggestions on where to start? Or any resources someone may have.  I am not even sure where to begin.  I have the pdf, cdf, variance, mean and moment generating function of the binomial distribution given to me but I am not sure how to use those.

REPLY [1 votes]: Hint: Fill up details in the following:
With $\;X\sim B(n,p)\;$ and using the identity $\;i\binom ni=n\binom{n-1}{i-1}\;$:
$$E(X^k)=\sum_{i=0}^n i^k\binom ni p^i(1-p)^{n-i}=\sum_{\color{red}{i=1}}^n i^k\binom ni p^i(1-p)^{n-i}=$$
$$=np\sum_{i=1}^n i^{k-1}\binom{n-1}
{i-1} p^{i-1}(1-p)^{n-i}\stackrel{m:=i-1}=np\sum_{m=0}^n (m+1)^{k-1}\binom{n-1}
m p^m(1-p)^{n-1-m}=$$
$$=np\,E\left[(Y+1)^{k-1}\right]\;\;,\;\;\;\text{with}\;\;Y\sim B(n-1,p)$$


TITLE: Counting all $n$ with $p\mid n^n -1$ for given $p$ prime
QUESTION [1 upvotes]: Say I have a prime $p$. I choose a number $n$ in the interval $[1, p^{p}]$ so that $p$ divides $n^{n}{-}1$. Now, can we quantify the cardinality of the set containing all possible values of $n$?

REPLY [2 votes]: The expression $n^n\bmod p$ has the base periodic with period $p$ and the exponent periodic with period $p-1$, therefore the expression $n^n\bmod p$ itself has period $p(p-1)$.
The solutions to $n^n\equiv1$ mod $p$ can be constructed from residues $n\equiv k$ mod $p$ by solving
$$ \begin{cases}
n\equiv k \bmod p \\ n\equiv 0 \bmod |k|
 \end{cases} $$
where $|k|$ is the multiplicative order of $k$ mod $p$. These solutions have period $p|k|$, so in the interval $[1,p(p-1)]$ there are $(p-1)/|k|$ such solutions, and the total number is
$$ f=\sum_{k\bmod p} \frac{p-1}{|k|}. $$
Note $k=0$ is excluded. The multiplicative group of integers mod $p$ is cyclic of order $m=p-1$, so there are $\phi(d)$ elements $k$ of order $|k|=d$ for every divisor $d\mid m$. So we may write
$$ f=m\sum_{d\mid m}\frac{\phi(d)}{d}. $$
Since $\phi(d)/d$ is multiplicative, so too is the sum as a function of $m$, so it suffices to evaluate for $m=q^s$ a prime power, which yields $\sum_{t=0}^s \phi(q^t)/q^t=1+s(1-1/q)$, so this expression is
$$ f=m\prod_{q\mid m}\left[1+v_q(m)\left(1-\frac{1}{q}\right)\right], $$
where $q$ runs over prime divisors of $m$.
Since $p^p\equiv p\bmod p(p-1)$, the # of solutions to $n^n\equiv 1$ mod $p$ in the interval $[1,p^p]$ is
$$ N=\frac{p^{p-1}-1}{p-1}f+g $$
where $g$ is the number of solutions in the interval $[1,p]$ (which I expect has no formula).


TITLE: solution of Given boundary value problem
QUESTION [0 upvotes]: For $\lambda\in \mathbb{R}$  consider the boundary value problem

$$x^2 \frac{d^2y}{dx^2}+2x\frac{dy}{dx}+\lambda y=0\;\;\;,y(1)=y(2)=0$$
called as $(P_{\lambda})$

Then i Have to prove which of following is right and which is wrong and why?

$1).$For any continuous function $f:[1,2]\to \mathbb{R}\;\;$with $f(x)\neq 0\;\;$for some $x \in[1,2]$ there $\\$ exist a solution $u$ of ($P_{\lambda}$)
$2).$There exist a $\lambda_0 \in \mathbb{R}$ such that ($P_{\lambda}$) has a nontrivial solution for any $\lambda>\lambda_0$

The solution i tried-
we can write the given differntial equation in form

$$\theta(\theta-1)+2\theta+\lambda=0\\ \theta^2+\theta+\lambda=0\\$$
which is quadratic in $\theta$

after solving this i get

$$\theta =\frac{-1 \pm \sqrt {1-4\lambda}}{2}$$

after that i solved further i get

$$\displaystyle y=c_1x^{\frac{-1 + \sqrt {1-4\lambda}}{2}}+c_2x^{\frac{-1 -\sqrt {1-4\lambda}}{2}}$$

further applying the boundary conditions i get  two conditions

$$c_1+c_2=0\;\; and\;\; c_1  2^{\frac{-1 + \sqrt {1-4\lambda}}{2}}+c_2 2^{\frac{-1 - \sqrt {1-4\lambda}}{2}}$$

for non trivial solution there Cofficents matrix determinent should not be zero. in end after all calculation i get

$$\lambda \neq \frac{1}{4}$$

after that i have no clue how to get to these options? how can i check which is true and why ?
Please help
Thankyou.

REPLY [2 votes]: Let $t:=\ln(x)$.  Then, $$\frac{\text{d}y}{\text{d}x}=\exp(-t)\,\frac{\text{d}y}{\text{d}t}\,.$$
That is,
$$x^2\,\frac{\text{d}^2y}{\text{d}x^2}=\exp(t)\,\frac{\text{d}}{\text{d}t}\,\left(\exp(-t)\,\frac{\text{d}y}{\text{d}t}\right)=\frac{\text{d}^2y}{\text{d}t^2}-\frac{\text{d}y}{\text{d}t}\,.$$
Therefore, the given differential equation now becomes
$$\frac{\text{d}^2y}{\text{d}t^2}+\frac{\text{d}y}{\text{d}t}+\lambda\,y=0\,.$$
If $\lambda<\dfrac14$, then the solutions are given by
$$\begin{align}y&=A_-\,\exp\left(\frac{-1-\sqrt{1-4\lambda}}{2}\,t\right)+A_+\,\exp\left(\frac{-1-\sqrt{1+4\lambda}}{2}\,t\right)\\&=A_-\,x^{\frac{-1-\sqrt{1-4\lambda}}{2}}+A_+\,x^{\frac{-1+\sqrt{1-4\lambda}}{2}}\,,\end{align}$$
where $A_-$ and $A_+$ are constants.
If $\lambda=\dfrac14$, then the solutions are given by
$$y=(a+b\,t)\,\exp\left(-\frac{1}{2}\,t\right)=\big(a+b\,\ln(x)\big)\,x^{-\frac12}\,,$$
where $a$ and $b$ are constants.  If $\lambda>\dfrac14$, then the solutions are given by
$$\begin{align}y&=\exp\left(-\frac{1}{2}\,t\right)\,\Biggl(C\,\cos\left(\frac{\sqrt{4\lambda-1}}{2}\,t\right)+S\,\sin\left(\frac{\sqrt{4\lambda-1}}{2}\,t\right)\Biggr)
\\&=x^{-\frac{1}{2}}\,\Biggl(C\,\cos\left(\frac{\sqrt{4\lambda-1}}{2}\,\ln(x)\right)+S\,\sin\left(\frac{\sqrt{4\lambda-1}}{2}\,\ln(x)\right)\Biggr)\,,\end{align}$$
where $C$ and $S$ are constants.
For $\lambda<\dfrac14$, if $y(x=1)=0$ and $y(x=2)=0$, then $$A_-+A_+=0\text{ and }A_-+A_+\,2^{\sqrt{1-4\lambda}}=0\,.$$
It follows that $A_-=A_+=0$, so $y$ is identically zero.  For $\lambda=\dfrac14$, if $y(x=1)=0$ and $y(x=2)=0$, then $$a=0\text{ and }a+b\,\ln(2)=0\,,$$ whence $a=b=0$ and so $y$ is again identically zero.  For $\lambda>\dfrac14$, if $y(x=1)=0$ and $y(x=2)=0$, then
$$C=0\text{ and }C\,\cos\left(\frac{\sqrt{4\lambda-1}}{2}\,\ln(2)\right)+S\,\sin\left(\frac{\sqrt{4\lambda-1}}{2}\,\ln(2)\right)=0\,.$$
This shows that $C=0$ and $S=0$, or $C=0$ and
$$\frac{\sqrt{4\lambda-1}}{2}\,\ln(2)=k\pi$$
for some positive integer $k$.  Thus,
$$\lambda=\frac{k^2\pi^2}{\big(\ln(2)\big)^2}+\frac{1}{4}\tag{*}$$
for some positive integer $k$.
That is, there exists a nonzero solution to $P_\lambda$ if and only if $\lambda$ is given by (*).  In that case, all solutions take the form
$$y=S\,x^{-\frac12}\,\sin\big(k\pi\,\log_2(x)\big)$$
where $S$ is a constant.  Hence, Option (2) is false.  I do not understand Option (1).


text:
\section{Scott normal form}
\label{sec:scott-normal-form}
In this appendix we prove that every $\fotwopres$ formula
can be converted into the normal form used in the body of the paper.

We will first give a couple of lemmas.

\begin{lemma}
\label{lem:scott-no-zero}
Let $S\subseteq \bbN_{\omega}$ where $0\notin S$
and $q$ be a unary predicate.
The following sentence $\Psi_1$:
\begin{align*}
\Psi_1 &:= \
\forall x \ \big(q(x)\ \to \ \exists^S y\ \phi(x,y)\big)
\end{align*}
is equivalent to $\Psi_2$:
\begin{align*}
\Psi_2 &:= \
\forall x \ \exists^{S\cup\{0\}}y \ \big(q(x)\wedge \phi(x,y)\big)
\ \wedge \
\forall x \ \exists^{\bbN_{\omega}-\{0\}}y \ \big(q(x)\to \phi(x,y)\big).
\end{align*}
\end{lemma}
\begin{proof}
It is worth noting that $q(x)\wedge \phi(x,y)$ is equivalent to
$(q(x)\to \phi(x,y))\wedge (\neg q(x)\to \myF)$.

Let $\cA$ be a structure.
For an element $a\in A$,
define $W_{a,\phi(x,y)}$ as follows:
\begin{align*}
W_{a,\phi(x,y)} & = \ \{b\in A \mid (\cA,x\mapsto a, y \mapsto b) \models \phi(x,y)\}.
\end{align*}
That is, $W_{a,\phi(x,y)}$ is the set of elements that can be assigned to $y$
so that $\phi(x,y)$ holds, when $x$ is assigned with element $a$.

Suppose $\cA \models \Psi_1$.
So, for every $a\in q^{\cA}$, $|W_{a,\phi}|\in S$, hence, the following holds:
\begin{align}
\label{eq:a-in-q}
\cA,a  \models  \exists^{S}y\ q(x)\to \phi(x,y)
\quad \text{and} \quad
\cA,a  \models \exists^{S}y\ q(x)\wedge \phi(x,y).
\end{align}
For every $a\notin q^{\cA}$, the following holds:
\begin{align}
\label{eq:a-not-in-q}
\cA,a \models \exists^{|A|} y \ q(x)\to \phi(x,y)
\quad \text{and} \quad
\cA,a  \models  \exists^{0} y \ q(x)\wedge \phi(x,y).
\end{align}
Combining (\ref{eq:a-in-q}) and (\ref{eq:a-not-in-q}), we have $\cA\models \Psi_2$.

For the other direction, suppose $\cA\models \Psi_2$.
Since $\cA\models \forall x \ \exists^{S\cup\{0\}}y \ \big(q(x)\wedge \phi(x,y)\big)$,
either  $|W_{a,\phi(x,y)}|=0$ or $|W_{a,\phi(x,y)}|\in S$, for every $a\in A$.
Since $\cA\models \forall x \ \exists^{\bbN_{\omega}-\{0\}}y \ (q(x)\to \phi(x,y))$,
for every $a\in q^{\cA}$, $|W_{a,\phi(x,y)}|\neq 0$.
Thus, for every $a\in q^{\cA}$,
$|W_{a,\phi(x,y)}|\in S$.
Therefore, $\cA \models \Psi_1$.
\end{proof}

The following lemma is proven in a similar manner.
\begin{lemma}
\label{lem:scott-with-zero}
Let $S\subseteq \bbN_{\omega}$ where $0\in S$
and $q$ be a unary predicate.
The sentence $\Psi_1$ below:
\begin{align*}
\Psi_1 &:= \
\forall x \ \big(q(x)\ \to \ \exists^S y\ \phi(x,y)\big)
\end{align*}
is equivalent to the following sentence $\Psi_2$:
\begin{align*}
\Psi_2 &:= \
\forall x \ \exists^{S}y \ \big(q(x)\wedge \phi(x,y)\big)
\end{align*}
\end{lemma}

Obviously, Lemma~\ref{lem:scott-no-zero} and~\ref{lem:scott-with-zero}
can be modified trivially when $q(x)$ is any quantifier-free formula
with free variable $x$.

\subparagraph*{Conversion into ``almost'' Scott normal form.}
We will first show how to convert an $\fotwopres$ sentence into an
equisatisfiable sentence in ``almost'' Scott normal form:
\begin{align}
\label{eq:snf-without-inequality}
& \forall x \forall y \ \alpha(x,y)
\ \wedge \ \bigwedge_{i=1}^k
\forall x \exists^{S_i} y \ \beta_i(x,y).
\end{align}
That is, the requirement $x\neq y$ is dropped for $\beta_i(x,y)$ to hold.
In fact,  we get more than equisatisfiability: each model of our sentence can
be expanded to a model of the normal form. This will be important for our result
about the spectrum. In the remainder of this section we omit similar statements for brevity.

The conversion is a rather standard renaming technique from two-variable logic.
Let $\Psi$ be an $\fotwopres$ sentence.
We first assume that $\Psi$ does not contain any subformula of the form $\forall x \phi$,
by rewriting them into the form $\exists^0 x \neg \phi$.

Whenever there is a subformula $\psi(x)$ in $\Psi$ of the form
$\exists^S y \ \phi(x,y)$,
where $\phi(x,y)$ is quantifier free and $S$ is a u.p.s.,
we perform a transformation.
Let $q$ be a fresh unary predicate, and replace the subformula $\psi(x)$ in $\Psi$ with atomic $q(x)$,
and add a sentence which states that $q(x)$ is equivalent to $\psi(x)$, i.e.,
\begin{align*}
& \forall x \ \big(q(x) \ \leftrightarrow \ \psi(x)\big),
\end{align*}
which is equivalent to
\begin{align*}
& \forall x \ \big(q(x) \ \to \ \exists^S y \ \phi(x,y)\big)
\quad \wedge \quad
\forall x \ \big(\neg q(x) \ \to \ \exists^{\bbN_{\omega}-S} y \ \phi(x,y)\big),
\end{align*}
which, in turn, by Lemma~\ref{lem:scott-no-zero} and~\ref{lem:scott-with-zero},
can be converted into sentences of the form~(\ref{eq:snf-without-inequality}).
We iterate this  procedure until $\Psi$ is in the ``almost'' Scott normal form described
above.

\subparagraph*{Conversion into Scott normal form in~(\ref{eq:snf}).}
Now, we show the conversion from ``almost'' Scott normal form into Scott normal form.
Note that
\begin{align*}
\forall x \exists^S y \ \beta(x,y)
\end{align*}
is equivalent to
\begin{align*}
& \forall x \big(\neg \beta(x,x) \ \to\ \exists^{S}y \ \beta(x,y) \wedge  x\neq y\big)
\quad\wedge \quad
\forall x \big(\beta(x,x) \ \to\ \exists^{S-1}y \ \beta(x,y) \wedge  x\neq y\big),
\end{align*}
where $S-1$ denotes the set $\{i-1 \mid i \in S\}$.

Applying Lemma~\ref{lem:scott-no-zero} and~\ref{lem:scott-with-zero},
a sentence of the form~(\ref{eq:snf-without-inequality}) can be converted into
an equisatisfiable sentence of the form:
\begin{align*}
& \forall x \forall y \ \alpha(x,y)
\quad \wedge \quad \bigwedge_{i=1}^k
\forall x \exists^{S_i} y \ \beta_i(x,y) \wedge x\neq y,
\end{align*}
where each $\beta_i(x,y)$ is quantifier free.
To make it into Scott normal form,
we introduce a new predicate $\gamma_i(x,y)$, for each $1\leq i \leq k$,
and rewrite the sentence as:
\begin{align*}
& \forall x \forall y \ \Big(\alpha(x,y)\wedge \bigwedge_{i=1}^k\big(\gamma_i(x,y)\leftrightarrow \beta_i(x,y)\big)\Big)
\ \wedge \ \bigwedge_{i=1}^k
\forall x \exists^{S_i} y \ \gamma_i(x,y) \wedge x\neq y.
\end{align*}

The conversion described above takes $O(Cn)$ time where
$n$ is the length of the original $\fotwopres$ sentence
and the factor $C$ is the complexity of computing the complement $\bbN_{\omega}-S$
of a u.p.s. $S$, which of course, depends on the representation of a u.p.s.
However, we should note that the number of new atomic predicates introduced
is linear in $n$.

config: arxiv