Ragnar
  • Member for 8 years, 5 months
  • Last seen more than a week ago
Induction without a base case
Accepted answer
43 votes

Suppose we want to prove $n=n+1$ for all (positive) integers $n$. We omit the base case. The induction hypothesis is $k=k+1$ for some $k\in \mathbb N$. Adding $1$ to both sides gives $k+1=k+1+1$, or $(...

View answer
How to solve $y = \sqrt{k\sqrt{k\sqrt{k \sqrt{k\sqrt{\dots}}}}}$?
Accepted answer
16 votes

We know that $$ y=\sqrt{k\cdot\sqrt{k\cdot\sqrt{\dots}}} $$ We can square the equation and divide by $k$: $$ \frac{y^2}k=\sqrt{k\cdot\sqrt{\dots}} $$ But the right hand side is just $y$ again, so we ...

View answer
N! ends with exactly 30 zeros?
10 votes

The number of zeros at the and of $n!$ is just the number of factors of $5$ in $n!$ (since the number of factors of $2$ in $n!$ is always larger than that). So, we need all $n$ such that the numbers $...

View answer
If $f(x)$ is discontinuous at $x=0$, can $\int_{-1}^1 f(x)dx$ exist.
Accepted answer
9 votes

In general, when $f$ and $g$ differ in (at most) a finite amount of points (in the interval $[a,b]$), we always have $$ \int _a^bf(x)\,dx=\int_a^b g(x)\,dx $$ This follows from the definition using ...

View answer
Consider the trace map $M_n (\mathbb{R}) \to \mathbb{R}$. What is its kernel?
Accepted answer
9 votes

The trace of a matrix $M$ is $0$ if and only if the sum of the elements on the (main) diagonal of $M$ is $0$. Since the dimension of all $n\times n$ matrices is $n^2$ and the dimension of its image $\...

View answer
If $a,b\in\mathbb R\setminus\{0\}$ and $a+b=4$, prove that $(a+\frac{1}{a})^2+(b+\frac{1}{b})^2\ge12.5$.
Accepted answer
8 votes

You can do this with the quadratic-arithmetic mean: (this is possible, because $a^2\geq 0$.) $$ \sqrt{\frac{a^2+b^2}2}\geq\frac{a+b}2\\ a^2+b^2\geq \frac{(a+b)^2}2=8 $$ Now, you only have to proof $\...

View answer
How can I show that $\left|\sum_{n=1}^\infty\frac{x}{n^2+x^2}\right|\leq\frac{\pi}{2}$ for any $x\in{\bf R}$?
8 votes

You can rewrite the sum to $$ \frac {1}{x}\sum_{n=1}^\infty \frac{1}{(\frac n x)^2+1} $$ Because $f(n)=\frac1{n^2+1}$ is strictly decreasing for positive (reals) $n$, we know that \begin{align} \frac ...

View answer
How to determine the Taylor Series for a polynomial?
Accepted answer
7 votes

For polynomials, the Taylor series around $x=0$ is just the polynomial itself. If you want the series around $x=a$, the general formula (for a function $f$ around $x=a$) $$ f(a)+f'(a)(x-a)+\frac{f''(a)...

View answer
Inequality using AM-GM
Accepted answer
6 votes

Using the substitution $a=\frac xy$, $b=\frac yz$ and $c=\frac zx$, we want to prove that $$ \sum_{cyc}\frac {xy}{z^2}\geq \frac xy+\frac yz+\frac zx $$ where we are taking cyclic sums. Using AM-GM, ...

View answer
Given a triangle find the length of BC
Accepted answer
6 votes

We are given that $∠BCD=θ$ and $∠BAD=2θ$. Also, $BD$ is the angular bisector of $∠ABC$. We draw the circle $\Gamma$ with center $A$ and radius $|AD|$. $G$ is the intersection of $\Gamma$ and $AB$ such ...

View answer
Derivative of $s = u^2 \iff\sqrt s = u$
Accepted answer
6 votes

Actually, they do: $$ s=u^2\\ \sqrt s=u $$ Differentiating: $$ ds=2u\,du\\ \frac{ds}{2\sqrt s}=du $$ Now, we can substitute $s=u^2$ in the second equation: $$ du=\frac{ds}{2\sqrt u}=\frac{ds}{2u} $$ ...

View answer
How do I put in words that $2\cos^2 x +\sin x-1$ cannot be factored?
Accepted answer
6 votes

you know that $\cos x^2+\sin x^2=1$. Because of this, the polynomial can be written as $$ 2(1-\sin^2 x)+\sin x-1=-2\sin ^2 x+\sin x +1=(2\sin x +1)(-\sin x+1) $$ EDIT When you do not want to use any ...

View answer
Ice cream combinatorics question
5 votes

This can be solved using the strategy used in this post: It comes down to calculating $$ \binom{5+3-1}{3}=\binom 73=\frac{7\cdot6\cdot5}{1\cdot2\cdot3}=35 $$ What we are doing is the following: We ...

View answer
Prove that $n^n \le (n!)^2$.
5 votes

HINT: Use the fact that $$ r (n+1-r) \geq n $$ (quadratic polynomial in $r$ with equality at $r=1$ and $r=n$) when $1\leq r\leq n$. Then, take the product over $r$: $$ \left(n! \right)^2=\prod_{r=1}^n ...

View answer
How to tackle a recurrence that contains the sum of all previous elements?
Accepted answer
5 votes

Since we only need and evaluate $T(n)$ when $n$ is a power of $2$, say that $a(k)=T(2^k)$. The recursion becomes (I will use $n$ again from now on): $$ a(n)=n2^n+\sum_{i=0}^{n-1}a(i) $$ Define $s(n)=\...

View answer
Software to draw easily sectors with angle on it
Accepted answer
5 votes

You can use Geogebra, a free program that can be used to created all kinds of geometric images, including this one. First create a circle with center $C$ and point on the circle $P$. Then make an ...

View answer
Why can't C(n,k) have a prime factor that is larger than n?
Accepted answer
5 votes

Since $\binom{n}{k}=\frac{n!}{k!(n-k)!}$, we know that any prime $p$ that divides $\binom nk$ also divides $n!$ (since dividing by integers can't add factors). Because $n!$ contains only factors $\...

View answer
Combinatorics with n case
Accepted answer
5 votes

Suppose you want to take an even number of books out of $2n$ books with you on your holiday. The left hand side sums the number of possibilities over all possible amounts $2k$ to take with you. On the ...

View answer
Show that ${n\choose r}2^r 3^{n-r}=\sum_{k=r}^{n} {n \choose k} {k \choose r}2^k$
Accepted answer
4 votes

We are going to show that both sides count the same number of possibilities and therefore have to be equal for the equation: $$ \binom nr 2^r3^{n-r}=\sum_{k=r}^n \binom nk\binom kr2^k $$ Suppose there ...

View answer
A combinatorics problem involving geometry
Accepted answer
4 votes

First, pick any starting point $A$. (Suppose it is at the bottom of the circle.) This can be done in $(2n+1)$ ways. Number the points starting at $A=0$. Let the second point $B$ be at position $i\leq ...

View answer
Graph colouring and maximal independent set
Accepted answer
4 votes

This is not true in general. Take the following graph $G$ for example: We can see that the maximal independent set $M$ consists of vertices $4$, $5$ and $6$. (If one of the center vertices is in $M$, ...

View answer
To provide a combinatorial argument for a combinatorics equality.
4 votes

Suppose we have $n+2$ books in a row numbered from $1$ to $n+2$ and we want to choose $m+2$ of them. Obviously, we can do that in $\binom {n+2}{m+2}$ ways, i.e. the right hand side of your equality. ...

View answer
Proving something using Pigeonhole Principle
4 votes

We know that $2^k\pmod n$ can only take a finite number of different values ($n-1$ to be precise, because $0$ is not possible). Since $k\in \mathbb N$ and $\mathbb N$ is infinite, there must be some ...

View answer
How I got this answer
Accepted answer
4 votes

Since Javes has more than $40$ books, he has at least $41$ books. Thus, Aslam has at least $5\cdot 41=205$ books. Since his number of books is a multiple of $4$ and $5$, it is a multiple of $20$. Thus,...

View answer
What is the difference between a $k$-degenerate graph and a graph with max vertex degree $k$?
Accepted answer
4 votes

A $k$-degenerate graph needs only to have (at least) one vertex of degree at most $k$ in every subgraph, while the maximum degree is the largest degree of all vertices, which is completely unrelated. ...

View answer
Help with Elementary number theory please
4 votes

You can use that \begin{align} a^{k+1}-1&=a(a^k-1)+(a-1)\\ &=a(a-1)(a^k+\cdots+a+1)+(a-1)\\ &=(a-1)(a^{k+1}+\cdots+a^2+a)+(a-1)\\ &=(a-1)(a^{k+1}+\cdots+a+1) \end{align} assuming you ...

View answer
Connected Graph
Accepted answer
4 votes

Suppose that $P$ and $Q$ are both longest paths (and thus have equal length $l$). Assume that they have no vertices in common. There are now two vertex-disjoint paths. Because the graph is connected, ...

View answer
How to calculate Taylor expansion of $\cos(\sin x)$
Accepted answer
4 votes

We know that for any $x$ (close to $0$): $$ \cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - O(x^6)\\ \sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - O(x^7) $$ We can find $\cos\sin x$ by substituting $x\...

View answer
If $(X_i)$ are i.i.d. exponential $\lambda$, then $\hat\lambda=n/\sum{X_i}$ is a biased estimator of $\lambda$
Accepted answer
4 votes

The distribution $X=\sum X$ is the Erlang distribution with parameters $\lambda$ and $n$. This distribution has the form $$ f(x;n,\lambda)=\frac{\lambda^n x^{n-1} e^{-\lambda x}}{\Gamma(x)} $$ (...

View answer
Solving matrix equation $AX = B$
4 votes

Write $B=(b_1,\dots,b_n)$ and $X=(x_1,\dots,x_n)$ with $b_i$ and $x_i$ the columns of $B$ and $X$ respectively. I assume you are able to solve $Ax=b$. Now, solve the $n$ linear equations $Ax_1=b_1$ to ...

View answer
1
2 3 4 5
8