combinatorics - Combinatorial Intuition Behind Binomial Identity

It isn't hard to algebraically show that:
$${n \choose k} = \sum_{j = r}^{n + r - k}{j - 1 \choose r - 1}{n - j \choose k - r}, 1 \leq r \leq k$$ I'm trying to find some sort of combinatorial "proof"/intuition as to why this is true. My thought is that it is similar to Pascal's Rule, but I'm not sure.

Thanks!

Answer

Clearly $\binom{n}k$ is the number of $k$-element subsets of $[n]=\{1,\ldots,n\}$. We can categorize these subsets according to their $r$-th smallest element. How many of them have $r$-th smallest element $j$? There are $j-1$ members of $[n]$ less than $j$, and we have to choose $r-1$ of them for our set; this can be done in $\binom{j-1}{r-1}$ ways. There are $n-j$ members of $[n]$ bigger than $j$, and we have to choose $k-r$ of them for our set; this can be done in $\binom{n-j}{k-r}$ ways. Thus, there are

$$\binom{j-1}{r-1}\binom{n-j}{k-r}$$

ways to choose a $k$-element subset of $[n]$ whose $r$-th smallest element is $j$. Summing over the possible values of $j$ yields the desired identity,

$$\sum_{j=r}^{n+r-k}\binom{j-1}{r-1}\binom{n-j}{k-r}=\binom{n}k\;.$$

Ratio test for convergent series - Does that mean that the series $1 +frac{1}{2} + frac{1}{3} +dotsb$ converges?

284. An infinite series is convergent if from and after some fixed term, the ratio of each term to the preceding term is numerically less than some quantity which is itself numerically less than unity.
     Let the series beginning from the fixed term be denoted by
     $$u_1+u_2+u_3+u_4+\dotsb,$$
     and let
     $$\frac{u_2}{u_1} where $r<1$.
     Then
     \begin{align*}
     
     &u_1+u_2+u_3+u_4+\dotsb\\
     &=u_1\left(1+\frac{u_2}{u_1}+\frac{u_3}{u_2}\cdot\frac{u_2}{u_1}+\frac{u_4}{u_3}\cdot\frac{u_3}{u_2}\cdot\frac{u_2}{u_1}+\dotsb\right)\\
     &\end{align*}
     that is, $<\frac{u_1}{1-r}$, since $r<1$.
     Hence the given series is convergent.

Does that mean that the series $1 +\frac{1}{2} + \frac{1}{3} +\dotsb$ should be a convergent one?
$$S_n = \frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dotsb$$

Here, we have
\begin{gather}
\frac{u_n}{u_{n-1}} = \frac{1/n}{1/(n-1)} = \frac{n-1}{n} = 1-\frac{1}{n}\\
∴\boxed{\frac{u}{u_{n-1}}<1}\\
∴\text{Series should be convergent}
\end{gather}

Answer

You need $\frac{u_n}{u_{n-1}} < r < 1$ for some $r < 1$ and all $n $.

For any $r <1$ we can find $r < \frac {u_n}{u_{n-1}} < 1$. So we can not find an appropriate $r <1$.

So we failed the hypothesis. The ratio test fails.

prime numbers - How to recognise the digit multiplication, subtraction or addition when checking for divisibility by 7, 11, 13, 17 and 19?

I was studying this page Divisibility by prime numbers under 50 to check for the divisibility by 7, 11, 13, 17, 19 etc. Is there any way to recognise whether to add or sub the given times of unit digit from the truncated number and to know how many times do I have to multiply with the unit digit.

For example:

to check for the divisibility by 7: subtract 2 times the unit digit from truncated number.

for 11: subtract 1 times

for 13: add 4 times the unit digit etc.

Answer

Yes, we can. Suppose we want to test a number $n$ for divisibility by $d$. Notice that we can expand $n$ with a result of $x$ after truncating the last digit $y$:
$$n=10x+y.$$
And we want to find some number $n'$ of the form $n'=x+\alpha y$ such $n'$ is divisible by $d$ exactly when $n$ is. For numbers not divisible by $2$ or $5$, there is an elegant solution to this; in particular, there is some number $\alpha$ such that $d$ divides $10\alpha - 1 $. Why this matters is then we can write

$$n'=\alpha n = 10\alpha x + \alpha y$$
which will be divisible by $d$ exactly when $n$ was ($\alpha$ and $d$ must be coprime, meaning that $k\alpha$ is divisible by $d$ exactly when $k$ was) but since $10\alpha = cd + 1$ for some integer $c$ (because $10\alpha -1$ is a multiple of $d$), we can write this as:
$$n'=(cd+1)x + \alpha y$$
and we can get rid of the $cd$ term, since it is divisible by $d$ and clearly if $n$ is divisible by $d$, so is $n-kd$ for any integer $k$. Thus, for our purposes, we can replace $n$ by $x+\alpha y$, getting rid of the $cdx$ term, without changing issues of divisibility by $d$.

This $\alpha$ term is the multiplicative inverse of $10$ mod $d$, which can be computed either by the Extended Euclidean algorithm, as described on the Wikipedia page. Trial and error would work too (you just need to find the first positive multiple of $d$ with a $9$ in the one's place or a negative multiple with a $1$ in the one's place). Notice that your existing identities follow this pattern; for $d=7$, we choose $\alpha=-2$, and $10\cdot (-2) - 1 = -21$, which is a multiple of $7$. Similarly, for $11$, we have $\alpha=-1$ and $10\cdot (-1) - 1 = -11$, which is a multiple of $11$ and, for $13$, we have $10\cdot 4 - 1 = 39$, which is a multiple of $13$.

So, for instance, to find a rule for $17$, we would notice that $-3\cdot 17= -51 = 10\cdot -5-1$. Thus, to compute divisibility by $17$, we chop off the unit digit $y$, and subtract $3y$ from the remaining number. To be very explicit, we can give the following general rules for divisibility tests of this form:

• If $d=10k + 1$, then subtract $k$ times the unit digit from the rest.


• If $d=10k + 3$, then add $3k+1$ times times the unit digit to the rest.


• If $d=10k + 7$, then subtract $3k+2$ times the unit digit from the rest.


• If $d=10k + 9$, then add $k+1$ times the unit digit to the rest.

Real and imaginary part of a complex sinusoid $y(t)=sin(wt)$

I'm trying to understand the plots on this page. It's a book about the Discrete Fourier Transform and it's discussing how a a function $x(t)=\cos(w_0t)$ or $y(t)=\sin(w_0t)$ is composed of a positive and a negative frequency component. I get why the spectrum of $\cos(wt)$ has two real components and none imaginary. But i don't get why $\sin(wt)$ have two imaginary components, as in b) of the following image.

This is the link for the image, from the web mentioned page, that i don't understand

I think i get how $x(t)=\cos(wt)$ is the sum of two complex sinusoids of frequencies of opposite signs that results in an zero imaginary part:

$$x(t)=\cos(wt)=\frac{e^{jwt}+e^{-jwt}}{2}$$
$$ x(t)=\frac{\cos(wt)+j\sin(wt)+\cos(-wt)+j\sin(-wt)}{2} $$

Since
$$\cos(-x)=\cos(x)$$

$$\sin(-x)=-\sin(x)$$

follows

$$ x(t)=\frac{\cos(wt)+j\sin(wt)+\cos(wt)-j\sin(wt)}{2} $$

so

$$Re\{ \ x(t)\ \} = \frac{\cos(wt)+\cos(wt)}{2}=\cos(wt)$$

and

$$Im\{ \ x(t)\ \} = \frac{\sin(wt)-\sin(wt)}{2}=0$$

That explains why $\cos(wt)$ have two real parts on the graph, of same amplitude and "opposite" frequencies.

I will try to to the same with $\sin(wt)$:

$$y(t)=\sin(wt)=\frac{e^{jwt}-e^{-jwt}}{2j}$$

Using $\cos(-x)=\cos(x)$

$$y(t)=\frac{ \cos(wt)+j\sin(wt) -(\cos(wt)+j\sin(-wt)) }{ 2j }$$
$$y(t)=\frac{ \cos(wt)+j\sin(wt) -\cos(wt)-j\sin(-wt) }{ 2j }$$

$$Re\{ \ y(t) \ \}=\frac{\cos(wt)-\cos(wt)}{2j}=0$$

$$Im\{ \ y(t) \ \}=\frac{\sin(wt)-\sin(-wt)}{2j}$$

I'm not sure how to follow from there. How come an imaginary part contains $j$? Or maybe $j$ should not be included? But in the case of

$$Im\{ \ y(t) \ \}=\frac{\sin(wt)-\sin(-wt)}{2}$$

Where that $j^-1$ went? This looks wrong to me because
$$j \cdot Im\{ \ y(t) \ \}\neq\frac{\sin(wt)-\sin(-wt)}{2j}$$

What did I do wrong here? This looks so silly, I'm sorry.

Answer

I think that the answer is less complex than you are making it.
Once you have:

$$\cos(\omega t)=\frac{e^{j \omega t}+e^{j (-\omega) t}}{2} $$
that shows that there is a '$\frac{1}{2}$' magnitude at '$\omega$' and a '$\frac{1}{2}$' magnitude at '$-\omega$', both in the positive real direction.

Taking the same logic:
$$\sin(\omega t)=\frac{e^{j \omega t}-e^{j (-\omega) t}}{2j} $$
Multiply both numerator and denominator of the fraction by $\frac{j}{2}$:
$$\sin(\omega t)=\frac{j\frac{1}{2} e^{j \omega t} - j\frac{1}{2} e^{j (-\omega) t}}{\frac{1}{2}\times 2j^2}$$
Where $j^2=-1$. This eliminates the denominator and multiplies the numerator by $-1$:
$$\sin(\omega t)=-j\frac{1}{2} e^{j \omega t} + j\frac{1}{2} e^{j (-\omega) t}$$
This shows that there is a '$-\frac{1}{2}j$' point at '$\omega$' and a '$(+)\frac{1}{2}j$' point at '$-\omega$'. In this case, both are in the imaginary plane. The one at positive $\omega$ has a negative sense, and the one at negative $\omega$ has a positive sense.

Does that help?

real analysis - Discontinuous derivative.

Could someone give an example of a ‘very’ discontinuous derivative? I myself can only come up with examples where the derivative is discontinuous at only one point. I am assuming the function is real-valued and defined on a bounded interval.

calculus - If a function such that $f(x+y)=f(x)+f(y)$ is continuous at $0$, then it is continuous on $mathbb R$

Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be a function such that $f(x+y)=f(x)+f(y)$. If $f$ is continuous at zero how can I prove that is continuous in $\mathbb{R}$.

real analysis - Let $q in mathbb{Q}$ and $x in mathbb{R}-mathbb{Q}$. Prove that $q+x in mathbb{R}-mathbb{Q}$

This is a homework problem for my Real Analysis course and I am having trouble getting started in the right direction. I understand the definition of the set of rational numbers and how $\mathbb{R}-\mathbb{Q}$ is the set of irrational numbers, but I am having trouble making the leap to where q+x is an element of the set of irrational numbers. Is there something that I'm missing?

I started with $a,b∈Q$ where either $a=0$ or $b=0$ which then gives us either $a+b=a$ or $a+b=b$. We know from this that $a+b∈Q$. It's the next part I'm struggling with.

Answer

You know $q$ is rational, so you can write $q = \dfrac{a}{b}$ for some integers $a,b$ where $b \neq 0$.

You also know that $x$ is irrational, so you cannot write $x$ as the ratio of two integers.

You need to show that $q+x$ is irrational. Suppose $q+x$ is rational, for the sake of contradiction.

Then, you can write $q+x = \dfrac{c}{d}$ for some integers $c,d$ where $d \neq 0$.

What does this tell you about $x$?