Questions tagged [faq]
This is meant for questions which are generalized forms of questions which get asked frequently. See tag details for more information.
110
questions
3
votes
1
answer
449
views
How to solve linear recurrence relations with constant coefficients.
As questions regarding sequences that verifies a linear recurrence relation with constant coefficients are posted very often on this site and that there appear to be no reference post about it, so I ...
- 24.6k
2
votes
2
answers
3k
views
Examples and Counterexamples of Relations which Satisfy Certain Properties
Definition: Given a set $X$, a relation $R$ on $X$ is any subset of $X\times X$. A relation $R$ on $X$ is said to be
reflexive if $(x,x) \in R$ for all $x \in X$,
irreflexive if $(x,x) \not\in R$ ...
- 24.2k
2
votes
5
answers
1k
views
Proving that among any $2n - 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$
How can one prove that among any $2n - 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$?
It is not hard to see this is equivalent to show that among $2n-1$ residue classes ...
- 39.5k
7
votes
3
answers
1k
views
How to solve homogeneous linear recurrence relations with constant coefficients?
Consider a sequence $(a_n)_{n\in\mathbb N}$ defined by $k$ initial values $(a_1,\dots,a_k)$ and
$$a_{n+k}=c_{k-1}a_{n+k-1}+\dots+c_0a_n$$
for all $n\in\mathbb N$.
What are some ways to get closed ...
2
votes
0
answers
67
views
Proof of reduced upper-tail inequality for standard normal distribution [duplicate]
X∼N(0,1), then to prove that for x>0,
$$ P(X>x)≤ \frac{1}{2}exp(−x^2/2) $$
I know how to prove the other two kinds of upper-tail inequality for standard normal distribution like this one
$$exp(−x^...
- 23
4
votes
1
answer
131
views
When does $p^2$ divide $an^k + bp$?
In the ongoing effort of dealing with abstract duplicates. This question is about the lemma:
Lemma Let $k \ge 2$, $p$ prime and $a$ coprime to $p$. Then $$p^2\!\mid a n^k+ bp\iff p\mid n,b.$$
...
- 25.5k
18
votes
1
answer
3k
views
Getting different answers when integrating using different techniques
Question: Is it possible to get multiple correct results when evaluating an indefinite integral? If I use two different techniques to evaluate an integral, and I get two different answers, have I ...
- 24.2k
6
votes
6
answers
887
views
What is the error in this fake proof which uses series to show that $1=0$?
A common "trick" for obtaining a closed form of a geometric series is to define
$$ R := \sum_{k=0}^{\infty} r^k, $$
then manipulate the series as follows:
\begin{align}
R - rR
&= \sum_{k=0}^{\...
- 24.2k
30
votes
6
answers
6k
views
How can a function with a hole (removable discontinuity) equal a function with no hole?
I've done some research, and I'm hoping someone can check me. My question was this:
Assume I have the function $f(x) = \frac{(x-3)(x+2)}{(x-3)}$, so it has removable discontinuity at $x = 3$. We ...
- 2,087
35
votes
7
answers
8k
views
Does an increasing sequence of reals converge if the difference of consecutive terms approaches zero?
If $a_n$ is a sequence such that
$$a_1 \leq a_2 \leq a_3 \leq \dotsb$$
and has the property that $a_{n+1}-a_n \to 0$, then can we conclude that $a_n$ is convergent?
I know that without the ...
- 704
1
vote
1
answer
68
views
Limit of an arithmetic average series
Sorry in advance as English is not my primary language.
I randomly thought of the following simple problem, and I coudn't solve it after one one hour trying. Maybe you guys can help.
Let $a_1$ and $...
0
votes
3
answers
61
views
Given $\langle f_{n}\rangle$ such that $f_{n}=\frac{f_{n-1}+f_{n-2}}{2}$ $\forall n\gt2$,to prove it converges to $\frac{f_1+2f_2}{3}$
If $\langle f_{n}\rangle$ be a sequence of positive numbers such that $$f_{n}=\frac{f_{n-1}+f_{n-2}}{2}$$ $\forall n\gt2$ ,then show that $\lt f_{n}\gt$ converges to $$\frac{f_1+2f_2}{3}$$
Replacing ...
- 804
22
votes
2
answers
33k
views
How to tell whether two graphs are isomorphic?
Suppose that we are given two graphs on a relatively small number of vertices. Here's an example:
Are these two graphs isomorphic? (That is: is there a bijection $f$ from $\{A,B,\dots,I\}$, the ...
- 114k
0
votes
2
answers
74
views
Proving a general rule which states where a recursive series converges
The recursive formula is
$t_n=\frac {t_{n-1}+t_{n-2}}2$
Changing $t_1$ and $t_2$ changes the number where the sequence converges as $n \to \infty$. With the help of everyone at StackExchange, I ...
- 21
-1
votes
3
answers
291
views
Limit of a mean sequence
The recursive formula is $$t_n=\frac {t_{n-1}+t_{n-2}}2$$ as $n$ approaches infinity the mean sequence converges at a certain number. Changing $t_1$ and $t_2$ changes the number where the sequence ...
- 21
10
votes
1
answer
6k
views
Eigenvalues of the principal submatrix of a Hermitian matrix
This question aims at creating an "abstract duplicate" of various questions that can be reduced to the following:
Let $A$ be an $n\times n$ Hermitian matrix and $B$ be an $r\times r$ principal ...
- 123k
4
votes
4
answers
1k
views
Find $6^{1000} \mod 23$ [duplicate]
Find $6^{1000} \mod 23 $
Having just studied Fermat's theorem I've applied $6^{22}\equiv 1 \mod 23 $, but now I am quite clueless on the best way to proceed.
This is what I've tried:
Raising ...
- 2,587
5
votes
1
answer
784
views
How Do I Compute the Eigenvalues of a Small Matrix?
If I have a $2\times 2$ or $3\times 3$ matrix, how should I go about computing the eigenvalues and eigenvectors of the matrix?
NB: I am making this question to provide a unified answer to questions ...
- 30.2k
2
votes
4
answers
262
views
Closed form for $\sum_{n=0}^{\infty} \binom{n+k}{k} x^n$ (Negative Binomial Theorem)
I was wondering if there is also a closed expression for the series
$$\sum_{n=0}^{\infty} \binom{n+k}{k} x^n$$ where $|x|<1.$
A few examples suggest that the answer is $\frac{1}{(1-x)^{k+1}}$ ...
user296837
0
votes
1
answer
127
views
Sterling Numbers of The Second Kind With Limitations Placed on Boxes/Parts
I know there are similar problems already on the board. However, none of the previously stated questions contain problems where limitations are placed on the BOXES.
Thus, seeing that I am struggling ...
- 105
69
votes
18
answers
18k
views
Proof of the hockey stick/Zhu Shijie identity $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$
After reading this question, the most popular answer use the identity
$$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$
What's the name of this identity? Is it the identity of the Pascal's triangle ...
- 1,530
3
votes
3
answers
185
views
Proving $n! > n^3$ for all $n > a$
Prove by induction: Find a, and prove the postulate by mathematical induction.
$$\text{For all}~ n > a,~ n! > n^3$$
Where ! refers to factorial.
So far I've done a bit of it, I'll skip right ...
- 89
3
votes
7
answers
737
views
Alternate ways to prove that $4$ divides $5^n-1$
I was working for various method to solve this:
For all $n\in \mathbb N$: $4\;\mid\;(5^{n}-1)$.
My try was:
1st: $$n=1 \to 4|5^1-1\\n \geq 2 \to 5^n=25,125,625,3125,...\\ n\geq 2 \to 5^n=\...
- 23k
21
votes
9
answers
3k
views
Summation Theorem how to get formula for exponent greater than 3
I'm studying in the summer for calculus 2 in the fall and I'm reading about summation. I'm given these formulas:
\begin{align*}
\sum_{i=1}^n 1 &= n, \\
\sum_{i=1}^n i &= \frac{n(n+1)}{2},\\
\...
- 361
12
votes
1
answer
3k
views
Volume of the intersection of two cylinders
I have two infinite cylinders of unit radius
in $\mathbb{R}^3$, whose axes are skew lines.
Say that the axis of one is centered on the $x$-axis, and the axis of the
other is determined by the two ...
- 29.4k
1
vote
2
answers
9k
views
Find $11^{644} \mod 645$ [duplicate]
Can someone just explain to me the basic process of what is going on here? I understand everything until we start adding 1's then after that it all goes to hell. I just need some guidance. The Problem ...
- 1,600
4
votes
5
answers
804
views
Proof of convergence of a recursive sequence
How do I prove that
$x_{n+2}=\frac{1}{2} \cdot (x_n + x_{n+1})$
$x_1=1$
$x_2=2$
is convergent?
- 131
0
votes
1
answer
2k
views
Volume of Intersection of cylinders (different radii)
I want to derive a formula for the area of the intersection of two rigth cylinders with different radii. To get an idea I attached a sketch.
My idea is to determine the borders of $x$ and $z$ in ...
- 180
2
votes
6
answers
598
views
Prove by induction that $n^2<n!$
How can I show that $n^2<n!$ for all $n\geq 4$
Step 1
For $n=1$, the LHS=$4^2=16$ and RHS=$4!=24$. So LHS$<$ RHS.
Step 2
Suppose the result be true for $n=k$ i.e.,
$k^2<k!$
Step 3
For $n=k+1$...
- 21
16
votes
3
answers
32k
views
An element of a group has the same order as its inverse
If $a$ is a group element, prove that $a$ and $a^{-1}$ have the same order.
I tried doing this by contradiction.
Assume $|a|\neq|a^{-1}|$
Let $a^n=e$ for some $n\in \mathbb{Z}$ and $(a^{-1})^m=e$ ...
- 179
4
votes
4
answers
3k
views
How to compute $3^{2003}\pmod {99}$ by hand? [duplicate]
Compute $3^{2003}\pmod {99}$ by hand?
It can be computed easily by evaluating $3^{2003}$, but it sounds stupid. Is there a way to compute it by hand?
- 691
3
votes
2
answers
675
views
How To Prove:$\sum_{n=1}^{\infty} \frac{(-1)^n}{n^4} = -\frac{7}{{720}}{\pi ^4}$
When I tried to solve this integral:
$$\int_0^\infty {\frac{{{x^3}}}{{1 + {e^x}}}} \;{\rm{d}}x$$
I had trouble computing the sieries:
$$\sum_{n=1}^{\infty} \frac{(-1)^n}{n^4}$$
Thanks.
- 835
1
vote
1
answer
71
views
Will this series converge? If so, what is its limit?
If $a_n=(a_{n-1}+a_{n-2})/2$ and $a_1, a_2$ are given, will this series converge? And if so, what is the limit?
By intuition I think it converges to $(a_1+2a_2)/3$ , but I am not able to prove it.
- 3,558
3
votes
4
answers
746
views
Calculating volume enclosed using triple integral
Calculate the volume enclosed between $x^2 + y^2=1$, $y^2+z^2=1$, $x^2+z^2=1$
I am supposed to solve this question using multiple integral. I am not able to visualize the resultant figure of whose I ...
user88923
68
votes
2
answers
9k
views
Determinant of a rank $1$ update of a scalar matrix, or characteristic polynomial of a rank $1$ matrix
This question aims to create an "abstract duplicate" of numerous questions that ask about determinants of specific matrices (I may have missed a few):
Characteristic polynomial of a matrix ...
- 108k
11
votes
1
answer
7k
views
Single Variable Calculus Reference Recommendations
This question is a generalization of the common question asking for calculus references. It is here to abstract away the repetition, and give a canonical resource for calculus references.
I'm ...
8
votes
3
answers
12k
views
Find the Mean for Non-Negative Integer-Valued Random Variable
Let $X$ be a non-negative integer-valued random variable with finite mean.
Show that
$$E(X)=\sum^\infty_{n=0}P(X>n)$$
This is the hint from my lecturer.
"Start with the definition $E(X)=\sum^\...
- 464
2
votes
5
answers
5k
views
Find a closed form for $\sum_{k=0}^{n} k^3$ [duplicate]
Find a closed form for $\sum_{k=0}^{n} k^3$.
I would appreciate ideas for approaching questions like this in general as well.
Thanks.
7
votes
1
answer
3k
views
Different ways of Arranging balls in boxes
This question is generalization of different cases of combinatorics problems that are generally asked.
We will find general way of arranging $n$ balls in $r$ boxes. Cases :
Identical Balls.
...
- 5,950
6
votes
3
answers
517
views
For a finite group of order $2n$ does there exist $x$ such that $x\ast x=e$? [duplicate]
Let $ (G,\ast)$ be a group with identity $e$ and cardinality $2n$ for some $n\in\omega$. Then, does there exist $x\in G$ such that $x\ast x=e$ and $x\neq e$?
- 1,519
11
votes
3
answers
44k
views
How many equivalence relations on a set with 4 elements.
Let S be a set containing 4 elements (I choose {$a,b,c,d$}). How many possible equivalence relations are there?
So I started by making a list of the possible relations:
{$(a,a)(a,b)(a,c)(a,d)(b,a)(b,...
- 231
7
votes
9
answers
7k
views
Show that if $n>2$, then $(n!)^2>n^n$.
Show that if $n>2$, then $(n!)^2>n^n$.
My work:
I tried to apply induction.
So, at the induction step, I need to prove,
$n^n>(n+1)^{n-1}$
Here, I tried to use induction again without any ...
- 6,140
13
votes
7
answers
55k
views
Find the volume common to two circular cylinders, each with radius r, if the axes of the cylinders intersect at right angles. (using disk/washer)
Find the volume common to two circular cylinders, each with radius r, if the axes of the cylinders intersect at right angles. (using disk/washer)
I saw no example of this problem anywhere.. I saw an ...
- 1,345
41
votes
5
answers
6k
views
Can $\sqrt{n} + \sqrt{m}$ be rational if neither $n,m$ are perfect squares?
Can the expression $\sqrt{n} + \sqrt{m}$ be rational if neither $n,m \in \mathbb{N}$ are perfect squares? It doesn't seem likely, the only way that could happen is if for example $\sqrt{m} = a-\sqrt{n}...
- 4,420
131
votes
1
answer
25k
views
Overview of basic facts about Cauchy functional equation
The Cauchy functional equation asks about functions $f \colon \mathbb R \to \mathbb R$ such that
$$f(x+y)=f(x)+f(y).$$
It is a very well-known functional equation, which appears in various areas of ...
11
votes
3
answers
2k
views
Showing that $a^n - 1 \mid a^m - 1 \iff n \mid m$
Let $a\ge 2$ be an integer. Show that for positive integers $m,n$, we have $a^n - 1$ divides $a^m - 1$ if and only if $n$ divides $m$.
I am having trouble showing this. I've seen a similar problem on ...
- 217
5
votes
3
answers
1k
views
Rigorous proof that $\int_{\Omega}X\;dP=\int_{-\infty}^{\infty}xf(x)\;dx$
I'm trying to prove rigorously that $\int_{\Omega}X\;dP=\int_{-\infty}^{\infty}xf(x)\;dx$. Where $f$ is the pdf of the random variable $X$.
I can't find a proof on the wikipedia article, or if it's ...
- 7,077
172
votes
4
answers
62k
views
Overview of basic results about images and preimages
Are there some good overviews of basic facts about images and inverse images of sets under functions?
50
votes
13
answers
28k
views
About $\lim \left(1+\frac {x}{n}\right)^n$
I was wondering if it is possible to get a link to a rigorous proof that
$$\displaystyle \lim_{n\to\infty} \left(1+\frac {x}{n}\right)^n=\exp x$$
- 679
27
votes
10
answers
54k
views
How to determine equation for $\sum_{k=1}^n k^3$
How do you find an algebraic formula for $\sum_{k=1}^n k^3$? I am able to find one for $\sum_{k=1}^n k^2$, but not $k^3$. Any hints would be appreciated.
- 606