Tuesday, 11 September 2018

combinatorics - Evaluate $sum_{k=1}^nfrac{1}{k}binom{n}{k}$





I'm interested in finding a nice closed form expression for the sum $\sum_{k=1}^n\frac{1}{k}\binom{n}{k}$. I've tried using the Binomial Theorem to get
\begin{align*}
\sum_{k=1}^n\frac{1}{k}\binom{n}{k}x^k & =\int_0^1\frac{(1+x)^n-1}{x} \, dx\\
&=\int_1^2 (1+u+\cdots+u^{n-1}) \, du
\end{align*}

using the substitution $u=1+x$ but I can't quite to simplify this integral either. I have also not been able to come up with a combinatorial approach, which may not exist since the summation and its terms are in general not integers. Any help in evaluating this sum would be appreciated, thanks!


Answer



In the question, the problem is in "nice closed form expression" since
$$\sum_{k=1}^n\frac{1}{k}\binom{n}{k}x^k=n x \, _3F_2(1,1,1-n;2,2;-x)$$ where appears an hypergoemetric function.



So, let us forget the $x$ and compute for a few values of $n$
$$S_n=\sum_{k=1}^n\frac{1}{k}\binom{n}{k}$$
$$\left\{1,\frac{5}{2},\frac{29}{6},\frac{103}{12},\frac{887}{60},\frac{1517}{60},\frac{18239}{420}\right\}$$ which are
$$\left\{1,\frac{5}{2},\frac{29}{6},\frac{206}{24},\frac{1774}{120},\frac{18204}{720},\frac{218868}{5040}\right\}$$ The denominators are clearly $n!$ and the numerators corresponds to sequence A103213 in OEIS.



As you will see in the link is that, for large $n$

$$S_n\approx \frac{2^{n+1}} n$$ It is also given that
$$S_n=-H_n-\Re(B_2(n+1,0))$$ where appear the harmonic number and the real part of the incomplete beta function.



Update



Concerning the asymptotic behavior, it seems that it could be slightly improved using
$$S_n\approx 2^{n+1} n^{\frac{1}{4 n}-1}$$


polynomials - Multiplicative Inverse in a $256$ Galois Field



I am working on finding the multiplicative reverse in $GF(2^8)$ using the Euclidean Algorithm but after reading multiple sources, I feel as though I am proceeding incorrectly. Using the irreducible polynomial $m(p)=x^8+x^4+x^3+x+1=0x11B$ I am trying to find the inverse of $x^6+x^4+x+1=0x53$



I know using long division (via http://www.wolframalpha.com/widgets/view.jsp?id=f396eaca9aaccbf858652bccc972324a) I get for the first step
$$(x^8+x^4+x^3+x+1)=(x^6+x^4+x+1)*(x^2-1)+(2x^4-x^2+2x+2)$$
but do I keep the negatives and even coefficients? I can't seem to get a reasonable answer and all the examples I have seen use simpler numbers. I know the answer to be $x^7+x^6+x^3+x=0xCA$ I just cannot seem to get there.


Answer



Here are the steps you should obtain.




\begin{align}
&x^8+x^4+x^3+x+1 = (x^6+x^4+x_1+1) (x^2 + 1) + x^2\\
&x^6+x^4+x+1 = x^2 (x^4 + x^2) + x + 1\\
&x^2 = (x+1) x + 1.
\end{align}


calculus - Finding the Derivative of |x| using the Limit Definition



Please Help me derive the derivative of the absolute value of x using the following limit definition.
$$\lim_{\Delta x\rightarrow 0}\frac{f(x+\Delta x)-f(x)}{\Delta x}
$$

I have no idea as to how to get started.Please Help.



Thank You


Answer



Since the absolute value is defined by cases,
$$|x|=\left\{\begin{array}{ll}
x & \text{if }x\geq 0;\\
-x & \text{if }x\lt 0,
\end{array}\right.$$
it makes sense to deal separately with the cases of $x\gt 0$, $x\lt 0$, and $x=0$.




For $x\gt0$, for $\Delta x$ sufficiently close to $0$ we will have $x+\Delta x\gt 0$. So
$f(x)= |x| = x$, and $f(x+\Delta x) = |x+\Delta x| = x+\Delta x$; plugging that into the limit, we have:
$$\lim_{\Delta x\to 0}\frac{f(x+\Delta x) - f(x)}{\Delta x} = \lim_{\Delta x\to 0}\frac{|x+\Delta x|-|x|}{\Delta x} = \lim_{\Delta x\to 0}\frac{(x+\Delta x)-x}{\Delta x}.$$
You should be able to finish it now.



For $x\lt 0$, for $\Delta x$ sufficiently close to zero we will have $x+\Delta x\lt 0$; so $f(x) = -x$ and $f(x+\Delta x) = -(x+\Delta x)$. It should again be easy to finish it.



The tricky one is $x=0$. I suggest using one-sided limits. For the limit as $\Delta x\to 0^+$, $x+\Delta x = \Delta x\gt 0$; for $\Delta x \to 0^-$, $x+\Delta x = \Delta x\lt 0$; the (one-sided) limits should now be straightforward.


Monday, 10 September 2018

definite integrals - How to show that $ PV int_{-infty}^{infty} frac{tan x}{x}dx = pi$



In a recent question, it was stated in a comment, without proof, that



$$ PV \int_{-\infty}^{\infty} \frac{\tan x}{x}dx = \pi$$




What is the easiest way to prove this? I was able to show that



$$
PV \int_{-\infty}^{\infty} \frac{\tan x}{x}dx = -PV\int_{-\infty}^{\infty} \frac{1}{x \tan x}dx \\
PV \int_{-\infty}^{\infty} \frac{1}{x \sin x}dx = 0 \\
\int_{-\infty}^{\infty} \frac{\sin x}{x}dx = \pi
$$



but failed to compute the original integral from this.



Answer



The
question is : What would be a right way to define the principal value
of this integral, knowing that it has infinitely many singularities at
the points $\frac{\pi}{2}+\pi\Bbb{Z}$ ? I will propose the following
$$
PV\int_0^\infty\frac{\tan x}{x}dx~\buildrel{\rm def}\over{=}~
\lim_{\lambda\to0}\int_0^{\infty}\frac{\sin
x\cos x}{x(\cos^2 x+\lambda^2)}dx
$$

Next I will show that the limit in this definition does exist and that
its value is $\frac{\pi}{2}$.



First, note that the convergence of the integral
$\int_0^{\infty}\frac{\sin x\cos x}{x(\cos^2 x+\lambda^2)}dx$ is easy to prove
using integration by parts. Now
$$\eqalign{
\int_0^{\infty}\frac{\sin x\cos x}{x(\cos^2 x+\lambda^2)}dx
&=\frac{1}{2}\lim_{n\to\infty}\int_{-\pi n}^{\pi (n+1)}\frac{\sin
x\cos x}{x(\cos^2 x+\lambda^2)}dx\cr

&=\frac{1}{2}\lim_{n\to\infty}\sum_{k=-n}^{n}\int_{\pi
k}^{\pi(k+1)}\frac{\sin x\cos x}{x(\cos^2 x+\lambda^2)}dx\cr
&=\frac{1}{2}\lim_{n\to\infty}\sum_{k=-n}^{n}\int_{0}^{\pi}\frac{\sin
x\cos x}{(x+ \pi k)(\cos^2 x+\lambda^2)}dx\cr
&=\frac{1}{2}\lim_{n\to\infty}\int_{0}^{ \pi}\left(\sum_{k=-n}^{n}\frac{1}{x+ \pi
k}\right)
\frac{\sin x\cos x}{ \cos^2x+\lambda^2}dx\cr
&=\frac{1}{2}\lim_{n\to\infty}\int_{0}^{ \pi}U_n(x)
\frac{ \cos^2 x}{ \cos^2x+\lambda^2}dx\cr
}

$$
where
$$
U_n(x)=\tan(x)\left(\sum_{k=-n}^{n}\frac{1}{x+ \pi
k}\right)
$$
But using the well-known expansion of the cotangent function, it is easy to see that
$\{U_n \}_n$ converges point-wise to $1$, and that this sequence is bounded uniformely on the interval $[0,\pi]$. Thus, we can interchange the signs of integral and limit in the above formula to get
$$
\int_0^{\infty}\frac{\sin x\cos x}{x(\cos^2 x+\lambda^2)}dx

=\frac{1}{2} \int_{0}^{ \pi}
\frac{ \cos^2 x}{ \cos^2x+\lambda^2}dx
= \int_{0}^{ \pi/2}
\frac{ \cos^2 x}{ \cos^2x+\lambda^2}dx
$$
Finally, taking the limit as $\lambda\to0$ we get
$$
PV\int_0^\infty\frac{\tan x}{x}dx~=~
\lim_{\lambda\to0}\int_0^{\infty}\frac{\sin
x\cos x}{x(\cos^2 x+\lambda^2)}dx=\frac{\pi}{2}.

$$


calculus - Prove $int^infty_0 bsin(frac{1}{bx})-asin(frac{1}{ax}) = -ln(frac{b}{a})$ using Frullani integrals

Prove $$\int^\infty_0 b\sin(\frac{1}{bx})-a\sin(\frac{1}{ax}) = -\ln(\frac{b}{a})$$




I'm supposed to use Frullani integrals which states that $\int^\infty_0 \frac{f(bx)-f(ax)}{x}\mathrm dx$ since this equals $[f(\infty)-f(0)] \ln(\frac{b}{a})$



So I need to get the first equation into the form of the Frullani integral. I can't figure out how to make this transformation though because I'm no good at them.

algebra precalculus - Compound interest coumpounded n time per year formula. $A=Pleft(1+frac{r}{n}right)^{nt}$ intuition behind it.

I know that the compound interest formula for the interest compounded annually is given by $$A=P(1+r)^t$$
I know the intuition behind it. But why the compound interest formula for the interest compounded n time per year is: $$A=P\left(1+\frac{r}{n}\right)^{nt}$$
What's the intuition behind it and why is it true?

calculus - Proving $limlimits_{n to infty} frac{n^a}{c^n} = 0$ using L'Hôpital's Rule



I am trying to prove $\displaystyle \lim_{n \to \infty} \frac{n^a}{c^n} = 0$ using L'Hôpital's Rule, but I'm stuck.




Here's what I have so far:



$$ \lim_{n \to \infty} \frac{n^a}{c^n} = \lim_{n \to \infty}\frac{an^{n-1}}{c^n \ln c} = \lim_{n \to \infty}\frac{a(a-1)n^{a-2}}{c^n(\ln c)^2 + c^n \frac{1}{c}}$$



All three limits above seem to evaluate to $\frac{\infty}{\infty}$, so I feel like I'm not getting anywhere. Any ideas?




Edit: So, with the help of the hints below, I was able to figure out that



$$ \lim_{n \to \infty} \frac{n^a}{c^n} = \frac{a}{\ln c} \cdot \lim_{n \to \infty} \frac{n^{a-1}}{c^n} = \frac{a}{\ln c} \cdot \frac{a - 1}{\ln c} \cdot \lim_{n \to \infty} \frac{n^{a-2}}{c^n} = \cdots $$




So, disregarding the constant, it looks like the numerator keeps decreasing, while the denominator stays the same.



I can also see that if I let $a = 2$, for instance, I end up with $0$ after applying L'Hopital's $2$ times:



$$ \begin{aligned} \lim_{n \to \infty} \frac{n^2}{c^n} &\overset{LH}= \lim_{n \to \infty} \frac{2n}{c^n \ln c} \\ &= \frac{2}{\ln c} \lim_{n \to \infty} \frac{n}{c^n} \\&\overset{LH}= \frac{2}{\ln c} \lim_{n \to \infty} \frac{1}{c^n \ln c} \\ &= \frac{2}{(\ln c)^2} \lim_{n \to \infty} \frac{1}{c^n} \\ &= 0 \end{aligned} $$



So it seems reasonable to conclude that for an arbitrary $a > 0$, I will end up with $0$ after applying L'Hopital's $a$ times.



But I'm not sure how to go about using induction to prove it formally. I've only proven very simple sums by induction so far. Do I have to apply it to a product here?




Answer



I deleted my old answer, as it missed the point a bit (especially given the edits to the question). I'm going to expand on J.G.'s answer, since you seem to need a little extra help.



Let's prove $\lim_{n\to\infty} \frac{n^a}{c^n} = 0$, for $a \in \Bbb{R}$ and $c > 1$. (if $0 < c \le 1$, then the sequence does not tend to $0$, and for $c = 0$, the expression is undefined). We can tackle this in a number of cases, but the cases reduce back down to one case fairly easily, using the squeeze theorem.



Case 1: $a \in \Bbb{N}_0 = \{0, 1, 2, \ldots\}$, and $c > 1$
In this case, we use induction on $a$ (not $n$, as I originally suggested). When $a = 0$, then
$$\frac{n^a}{c^n} = \frac{1}{c^n}.$$
This tends to $0$, a fact which you seem happy to assume. If you wished to prove it, observe that the sequence $a_n = \frac{1}{c^n}$ satisfies is decreasing, bounded below by $0$, and hence convergent. It also satisfies the recurrence relation $a_{n+1} = \frac{a_n}{c}$, so if $L$ is its limit, then taking the limit of both sides yields $L = \frac{L}{c} \implies (c - 1)L = 0$, and hence $L = 0$, as $c \neq 1$.




You probably could skip the above proof, but either way, the base case is established.



Now, suppose for some $k \in \Bbb{N}_0$ (and $c > 1$), we have
$$\lim_{n \to \infty} \frac{n^k}{c^n} = 0.$$
Then,
\begin{align*}
\lim_{n \to \infty} \frac{n^{k+1}}{c^n} &= \lim_{n \to \infty} \frac{(k+1)n^k}{\ln c \cdot c^n} &\text{L'Hopital's rule} \\
&= \frac{k+1}{\ln c} \lim_{n \to \infty} \frac{n^k}{c^n} \\
&= \frac{k+1}{\ln c} \cdot 0 = 0 &\text{induction hypothesis.}
\end{align*}


By induction, we now have $\lim_{n \to \infty} \frac{n^a}{c^n} = 0$ for all $a \in \Bbb{N}_0$ and $c > 1$. That is, we have completed this case.



Case 2: $a \in \Bbb{R}$, and $c > 1$
To prove this case, simply choose any natural number $k$ such that $k \ge a$ (we can do this, due to the Archimedean property). Naturally, if we take a negative value of $a$, then just choose $k = 0$ (or $1$, or anything higher really). Then, note that for all $n$,
$$0 \le \frac{n^a}{c^n} \le \frac{n^k}{c^n}.$$
The first case proved that $\frac{n^k}{c^n} \to 0$. Thus, by squeeze theorem, we have a proof for case 2.



We can even extend to $c < -1$ too!



Case 3: $a \in \Bbb{R}$, and $c < -1$
We prove this again by squeeze theorem. Note that,
$$-\frac{n^a}{|c|^n} \le 0 \le \frac{n^a}{|c|^n},$$

and by case 2, both bounds tend to $0$, proving case 3.



Hope that helps, and sorry for the misleading hint.


real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...