Questions tagged [faq]

This is meant for questions which are generalized forms of questions which get asked frequently. See tag details for more information.

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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^...
user avatar
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.$$ ...
user avatar
  • 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 ...
user avatar
  • 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}^{\...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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}}$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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=\...
user avatar
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},\\ \...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
  • 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$...
user avatar
  • 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$ ...
user avatar
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?
user avatar
  • 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.
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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^\...
user avatar
  • 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.
user avatar
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. ...
user avatar
  • 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$?
user avatar
  • 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,...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$$
user avatar
  • 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.
user avatar