summation - Find closed form of sum of fraction of binomial coefficients

can somebody give me a hint for this exercise, where I have to find the specific closed form?

$\sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}}, m,n\in\mathbb{N}$ and $m\leq n$

What I have done so far:

$\sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}} = \sum_{k=0}^m \frac{\frac{m!}{(m-k)!\cdot k!}}{\frac{n!}{(n-k)!\cdot k!}} = \sum_{k=0}^m \frac{m!}{n!}\cdot \frac{(n-k)!}{(m-k)!} = \frac{m!}{n!}\cdot \sum_{k=0}^m \frac{(n-k)!}{(m-k)!}$

Look at example 1: $n=8, m=5$

$\frac{5!}{8!}\cdot(\frac{8!}{5!} + \frac{7!}{4!} +\frac{6!}{3!} +\frac{5!}{2!} + \frac{4!}{1!} +\frac{3!}{0!}) = \\\frac{5!}{8!} \cdot (8\cdot7\cdot6+7\cdot6\cdot5+6\cdot5\cdot4+5\cdot4\cdot3+4\cdot3\cdot2+3\cdot2\cdot1) = \\
\frac{5!}{8!} \cdot (336+210+120+60+24+6) = \frac{5!}{8!}\cdot 756 = 2.25$

I can't find a pattern.

Edit 1: Maybe there is an approach with recursion.

Edit 2: Okay I found the solution.

$\sum_{k=0}^m \frac{m!}{n!}\cdot \sum_{k=0}^m \frac{(n-k)!}{(m-k)!}= \frac{m!}{n!}\cdot\frac{1}{4}\cdot t\cdot(t+1)\cdot(t+2)\cdot(t+3)$ with $t=(n-m)!$

Edit 3: This formula works well for example 1, but fails for example 2: $n=9, m=3$

$\frac{3!}{9!}\cdot(\frac{9!}{3!} + \frac{8!}{2!} +\frac{7!}{1!} +\frac{6!}{0!}) = \\\frac{3!}{9!} \cdot (9\cdot8\cdot7\cdot6\cdot5\cdot4+8\cdot7\cdot6\cdot5\cdot4\cdot3+7\cdot6\cdot5\cdot4\cdot3\cdot2+6\cdot5\cdot4\cdot3\cdot2\cdot1) = \\
\frac{3!}{9!} \cdot (60480+20160+5040+720) = \frac{3!}{9!}\cdot 86400 = 1.428$

So I have still no general solution. Can someone help?

Answer

Let

$$S(m,n):=\sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}}$$

We are going to prove:
$$S(m,n)=\frac{n+1}{n+1-m}.\tag{1}$$

Obviously (1) is valid for $m=0$ and arbitray $n\ge 0$. Further, if (1) is valid for $(m-1,n-1)$ it is valid for $(m,n)$ as well:
$$
S(m,n):=1+\sum_{k=1}^m \frac{\frac mk\binom{m-1}{k-1}}{\frac nk\binom{n-1}{k-1}}
=1+\frac{m}{n} S(m-1,n-1)\\
\stackrel{I.H.}{=}1+\frac{m}{n}\frac{n}{n+1-m}=\frac{n+1}{n+1-m}.
$$

Thus by induction (1) is valid for arbitrary $0\le m \le n$.

linear algebra - Find a eigenvalues of matrix $A$ without using characteristic polynomial

Let $A$ be the following matrix:

$A=\begin{bmatrix}
4&1&-1\\
2&5& -2\\
1&1&2\\
\end{bmatrix}$

Find the eigenvalues of $A$ if you know that algebraic multiplicity of one eigenvalue is $2$. But you must not use characteristic polynomial.

I have no idea how to solve this, because if I use trace and determinant I still get polynomial with third degree so is still a characteristic polynomial. If I add $A^T$ on $A$ I get a symmetric matrix which is positive definite, so the eigenvalues are positive, so maybe I can use spectral theorem because $A+A^T$ is symmetric but I still need eigenvectors, so nothing from that. Do you know something?

Answer

Using the usual dodge of trying out a few simple linear combinations of the columns, one can quickly discover that by luck or by design, $(1,0,1)^T$ is an eigenvector with eigenvalue $3$. (I checked that combination first since the $2$ and $-2$ in the second row cancel.) Comparing this to $\operatorname{tr}A=11$, there are two possibilities: if $3$ is the double eigenvalue, then the other one must be 5; if the other eigenvalue is the double, then it must be $4$. Test these against $\det A$ to find the correct one.

Determining Convergence/Divergence of a Sequence

I am given a series defined by the following statement:

$a_n = $ the first digit in the decimal expression $n$

And so the sequence looks like this:

$1,2,3,4,5,6,7,8,9,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3$ etc.

I need to determine whether this sequence converges or diverges. My first instinct is simply to state that it is clearly infinite and non-repeating and so diverges. However I feel like there's a way to prove that is the case but can't figure out how since there's no general expression (that I can think of) for the sequence whose limit I can take.

Answer

for $n\geq1$, we have

$a_{10^n}=1$ and $a_{2.(10^n)}=2$.

two subsequences have two different limits, so the sequence $(a_n)$ is divergent.

What is the probability that it takes more than seven rolls of a fair $6$-sided die to roll a six?

What is the probability that it takes more than seven rolls of a fair $6$-sided die to roll a six?

The probability of rolling a six per roll is $1/6$. Therefore, the probability of rolling something other than a 6 is $5/6$.

So wouldn't the probability that you don't roll a six within the first $7$ rolls just be $(5/6)^7$?

modular arithmetic - What is the remainder when $5 000 000^{500 000 000 000}$ is divided by the prime number $10^{6}+3$?

What is the remainder when $5,000, 000^{500 ,000 ,000 ,000}$ is divided by the prime number $10^{6}+3$?

I tried to use Fermat's Little Theorem but the exponent is still pretty high.

calculus - Convergence of $sum_{n=0}^infty frac{cos(n)}{n}$

Does this series converge

$$\sum_{n=1}^\infty \frac{\cos(n)}{n}$$

someone has told me that I have to apply Dirichlet's test but I don't know how to calculate the sum

$$\left|\sum_{n=1}^{N} \cos(n)\right|$$

Answer

It is the finite sums that you have to bound (it does not imply that the series converges). You have
\begin{align}
\left|\sum_{n=1}^N\cos n\right|
& =\left|\sum_{n=1}^N \operatorname{Re}\,e^{in}\right|
=\left|\operatorname{Re}\,\sum_{n=1}^N e^{in}\right|
=\left|\operatorname{Re}\,\frac{e^{i}-e^{i(N+1)}}{1-e^i}\right| \\[10pt]
& \leq\left|\frac{e^{i}-e^{i(N+1)}}{1-e^i}\right|
\leq\frac2{|1-e^i|}
=\frac2{\sqrt{(1-\cos1)^2+\sin^21}}=\frac{\sqrt 2 }{\sqrt{1-\cos1}}

\end{align}

linear algebra - What can be said if $A^2+B^2+2AB=0$ for some real $2times2$ matrices $A$ and $B$?

Let $A,B\in M_2(\mathbb{R})$ be such that $A^2+B^2+2AB=0$ and $\det A= \det B$. Our goal is to compute $\det(A^2 - B^2)$. According to the chain of comments on Art of Problem Solving, the following statements are true:

1. $\det(A^2+B^2)+\det(A^2-B^2)=2(\det A^2+\det B^2)$. (Is this well known?)


2. (1) $\implies \det(A^2-B^2)=0$.


3. If $A,B\in M_2(\mathbb{C})$ satisfy $A^2+B^2+2AB=0$, then $AB=BA$.


4. $(A+B)^2=0 \implies \det(A^2-B^2)=0$.

Can someone help me with justifying these statements?

Edit:
Doug M provided an explanation for (1) in the answers. Here is an explanation for (2):

$A^2+B^2+2AB=O_2 \implies A^2+B^2=-2AB$. So $\det(A^2+B^2)=4\det(AB)$. Now using (1), $\det(A^2-B^2)= 2(\det(A^2)-2\det(AB)+\det(B^2)) = 2((\det(A)^2-\det(B)^2) = 0$.

Answer

Of course, the OP did not understand much about the proposed exercise. In particular, in $M_2(\mathbb{C})$, $A^2 +B^2+2AB=0$ implies $\det(A)=\det(B)$.

In fact, the interesting result is

Proposition. Let $A,B\in M_2(\mathbb{C})$ be such that $(1)$ $A^2+B^2+2AB=0$; then $AB=BA$. Note that the result works only in dimension $2$.

Proof. If $H=A+B$, then $H^2=HA-AH$ and $trace(H^2)=0$. Moreover $H^3=H^2A-HAH=HAH-AH^2$ implies that $trace(H^3)=0$. We deduce that the eigenvalues of $H$ are $0$, $H$ is nilpotent, $H^2=0$, $AH=HA$, $AB=BA$. $\square$

Remark. According to Proposition, $(1)$ implies that $(A+B)^2=0$, $\det(A+B)=0$, $\det(A^2-B^2)=0$; moreover $AB=BA$ implies that $A,B$ are simultaneously triangularizable; since $A+B$ is nilpotent, we may assume that $A=\begin{pmatrix}a&c\\0&b\end{pmatrix},B=\begin{pmatrix}-a&d\\0&-b\end{pmatrix}$ and, consequently, $\det(A)=\det(B)$.