elementary number theory - Validity of Inductive Proof - Proof Confirmation

I want to prove this statement using weak induction:

Every integer $n>11$ is a sum of two composite integers.

When I prove it I get stuck at something basic I believe but unclear for me:

I prove it separately for the odd $2n+1$ and the even $2n$ numbers:

$n$ must be: $n\ge6 (2*6>11)$

I'm stuck at the same thing for odd and even numbers so I'll ask it regarding the even ones.

I check the validity of the claim for the basic cases when $n=6$.
$2*6=12=6+6$. Indeed is a sum of two composites.

Then I assume it's true for $2n$ and check for $2(n+1)$:

Then i get stuck because $2(n+1)$ and $2n$ are the of same form.

So can I assert the claim is true for $2(n+1)$ because it's the same form as $2n$ and based on my induction assumption earlier its true for $2n$?

Answer

$2n = j + k$ ($m$ and $n$ composite)

$2(n + 1) = j + k + 2$.

If $j$ (or $k$) is even (well, if one is even they both are but I'll pretend we don't know that) then $j + 2$ (or $k + 2$) is even and thus composite. $2(n + 1) = (j + 2) + k$ (or $j + (k + 2)$); sum of composites.

If $j$ and $k$ are both odd then $j + 1$ and $k + 1$ are both even so $2(n + 1) = (j + 1) + (k + 1)$; sum of composites.

Possible permutations, how to work out the maths

I am interested in understanding how to calculate possible permutations. For example for a 24bit MAC address (made up) ad:ba:32:d5:f0:dd. I believe the highest possible value per octet would be FF. So the highest possible value for the last 3 octets would be FF:FF:FF, so would that be 16 to power of 16? or 16 x 16? As you may have guessed my maths is rather lacking so I would like to understand how this would work.

Possible Values Up To F

Can we pull out a constant of a divergent series?

I know that if a series converges, the following applies:

$$
\sum_{n=i}^\infty c a_n = c \sum_{n=i}^\infty a_n
$$

However, I can't seem to find any info on whether this holds for diverging series as well. The property is often mentioned together with this one, of which I know it does not apply to divergent series:

$$
\sum_{n=i}^\infty a_n + b_n= \sum_{n=i}^\infty a_n + \sum_{n=i}^\infty b_n
$$

This makes me think the first property might require the same condition, but I'm not sure.

combinatorics - Multiple sum involving binomial factors

Let $n$ and $m$ be positive integers and let $0 \le j \le n-m-1$. Show that:
\begin{align}
\sum\limits_{l=m}^{n-j-1} \binom{n-l-1}{j} \binom{l}{m} \binom{n+l}{j}
&=\sum\limits_{p=0}^j \sum\limits_{p_1=0}^j \sum\limits_{p_2=0}^m \frac{(p+p_1+p_2)!}{p! p_1! p_2!} \binom{j}{p_1} \binom{2n-j}{j-p}\\\hspace{1cm} &\times\binom{n-j+p}{m-p_2} \binom{n-j-m+p+p_2}{1+p+p_1+p_2} (-1)^{p+p_2}
\end{align}

I have derived it using methods from analysis and then I verified the result using Mathematica. This result is a generalisation of another result given in here A double sum with combinatorial factors .

elementary number theory - Show that $lim_{n rightarrow infty} left(prod_{i=1}^{n} (a_i+1) right)^{1/n} $ using Birkhoff Ergodic Theorem

Show that for Lebesgue-almost every $x \in [0,1)$, the geometric mean

$$\lim_{n \rightarrow \infty} \left(\prod_{i=1}^{n} (a_i+1) \right)^{1/n} $$

exists and has common value. What is this? (no proof required)

I think this has something to do with the Birkhoff ergodic Theorem

I tried $$\begin{align} \log \left( \lim_{n \rightarrow \infty} \left(\prod_{i=1}^{n} (a_i+1) \right)^{1/n} \right) &= \lim_{n \rightarrow \infty} \log\left(\prod_{i=1}^{n} (a_i+1) \right)^{1/n} \\
&= \lim_{n \rightarrow \infty} \frac{1}{n} \sum_{i=1}^{n} \log (a_i+1) \\
&= ....???
\end{align}$$

It was shown in the part before that if $x = \sum_{i=1}^{\infty}\frac{a_i}{10^i}$ where $a_i \in \{0,1,\dots,9 \}$ that for Lebesgue-almost every $x \in [0,1)$ that

$$\lim_{n \rightarrow \infty} \frac{1}{n} \sum_{i=1}^{n}a_i=\frac{9}{2} $$

but I cannot see how this can be used.

Answer

The $n$th term is $\exp(S_n(x)/n)$ where $$S_n(x)=\sum\limits_{k=1}^nX_k(x),\qquad X_k(x)=\log(1+a_k(x)).$$ With respect to the Lebesgue measure on $[0,1)$, the sequence $(a_k)$ is i.i.d. hence $(X_k)$ is i.i.d. and $S_n\to E(X_1)$ almost surely, by the strong law of large numbers for i.i.d. integrable sequences. Furthermore, $a_1$ is uniform on $\{0,1,\ldots,9\}$ hence $E(X_1)=\frac1{10}\sum\limits_{i=0}^9\log(1+i)=\frac1{10}\log(10!)$.
Thus, $\exp(S_n(x)/n)\to\ell$ for almost every $x$, where $$\ell=\exp(E(X_1))=(10!)^{1/10}\approx4.5287,$$ and in particular, $\ell\ne9/2$.

Nota: One may replace "the strong law of large numbers for i.i.d. integrable sequences" above by "Birkhoff ergodic theorem".

complex analysis - Use path integrals to solve another integral.

Let $f(z) = e^{-z^2/2}$ and $\gamma = \gamma_1 + \gamma_2 + \gamma_3 + \gamma_4$ be this path, where $a > 0$ and $R > 0$.

I need to show that
$$
\int_0^\infty e^{-t^2/2} \cos(at) dt = \sqrt{\frac{\pi}{2}} e^{-a^2/2}. \quad\quad (*)

$$

The first part of the exercise was to show that
$$
\lim_{R \to \infty}\int_{\gamma_2} f(z)dz = \lim_{R \to \infty}\int_{\gamma_4} f(z)dz = 0.
$$
I was able to do that. I can also use that $f$ has a primitive. Because $\gamma$ is closed it is also clear, that
$$
\lim_{R\to\infty} \int_{\gamma_1} f(z)dz + \lim_{R\to\infty} \int_{\gamma_3} f(z)dz = 0.
$$

I am unsure what to do next to solve the integral (*).

Answer

Let $\gamma_{1}$ be the curve $t$ for $t\in [-R,R]$ and $\gamma_{3}$ be the curve $ia -t$ for $t\in [-R,R]$.

Then

$$\lim_{R\rightarrow \infty}\int_{\gamma_{1}} f(z)\operatorname{d}\!z + \lim_{R\rightarrow\infty}\int_{\gamma_{2}} f(z) \operatorname{d}\!z = \lim_{R\rightarrow\infty} \int_{-R}^{R} e^{-t^{2}/2} - e^{-(ia-t)^{2}/2}\operatorname{d}\!t.$$

Now I'll leave it to you to calculate the LHS of

$$\operatorname{Re}\left[ \lim_{R\rightarrow\infty} \int_{-R}^{R} e^{-t^{2}/2} - e^{-(ia-t)^{2}/2}\operatorname{d}\!z\right] = 0$$

and proceed from there.

combinatorics - Closed form for a formula with a summation over $ibinom{n-i}{k-1}$, and combinatorial proof?

I was trying to simply an expression in an exercise related to randomized algorithms. Here is the expression which I have obtained at the end.

$$ \displaystyle\frac{\displaystyle\sum_{i=1}^{n+k-1} i \binom{n-i}{k-1}}{ \displaystyle{n \choose k}}$$

Is there any way to simplify the numerator so that the whole expression simplifies into a nice closed formula? A combinatorial approach would be greatly appreciated.

Answer

Consider the number of ordered pairs $(a, S)$ such that $S$ is a $k$-element subset of $\{1,2, \dots, n\}$ and $a \le \min S$.

One way of counting:

Fix $\min S$.

If $\min S = i$, the number of sets = $\binom{n-i}{k-1}$ (choose $k-1$ from $\{i+1, i+2, \dots, n\}$. For each such $S$, you have $i$ possibilities for $a$.

Thus the number of $(a,S)$ pairs = $\sum_{i=1}^{n-k+1} i\binom{n-i}{k-1}$

Now count that differently: either $a = \min S$ or not.

If $a \neq \min S$, then the number is $\binom{n}{k+1}$ (pick $k+1$ elements basically)

If $a = \min S$, the number is $\binom{n}{k}$.

Thus the numerator you seek is $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$

So your expression simplifies to $\dfrac{n+1}{k+1}$.

(Note, I have assumed you wanted the sum upto $n-k+1$)