List of Generalisations of Common Questions

Question

Here is a list of generalised faqs to which other questions may be deduped against, split by topic (please edit the question).

---

Arithmetic arithmetic

• Laws of signs (minus times minus is plus): Why is negative times negative = positive?

• Order of operations in arithmetic: What is the standard interpretation of order of operations for the basic arithmetic operations?

---

Algebra/Precalculus algebra-precalculus

• Solving equations with multiple absolute values: What is the best way to solve an equation involving multiple absolute values?

• Extraneous solutions to equations with a square root: Is there a name for this strange solution to a quadratic equation involving a square root?

• Principal $n$-th roots:

  • Significance of $\sqrt[n]{a^n} $?!
  • Why is the even root of a number always positive?
  • Also see “Exponentiation” below

• $0! = 1$: Prove $0! = 1$ from first principles

• Partial fraction decomposition of rational functions: Converting multiplying fractions to sum of fractions

• Highest power of a prime $p$ dividing $N!$, number of zeros at the end of $N!$ and related questions: Highest power of a prime $p$ dividing $N!$

Exponentiation exponentiation

• Solving $x^x=y$ for $x$: Is $x^x=y$ solvable for $x$?
• What is the value of $0^0$? Zero to the zero power – is $0^0=1$?
• Why $\sqrt{-1 \times -1} \neq \sqrt{-1}^2$?
• Why $(-2)^{2.5}$ isn't equal to $((-2)^{25})^{1/10}?\,$ [Fractional powers of negative numbers]

---

Calculus calculus

• Indefinite integrals obtained using different techniques appear different (but are actually the same up to a constant): Getting different answers when integrating using different techniques

• Integrating polynomial and rational expressions of $\sin x$ and $\cos x$: Evaluating $\int P(\sin x, \cos x) \text{d}x$

• Integration using partial fractions: Integration by partial fractions; how and why does it work?

• Intuitive meaning of Euler's constant $e$: Intuitive Understanding of the constant "$e$"

• Evaluating limits of the form $\lim_{x\to \infty} P(x)^{1/n}-x$ where $P(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_0$ is a monic polynomial: Limits: How to evaluate $\lim\limits_{x\rightarrow \infty}\sqrt[n]{x^{n}+a_{n-1}x^{n-1}+\cdots+a_{0}}-x$

• Finding the limit of rational functions at infinity: Finding the limit of $\frac{Q(n)}{P(n)}$ where $Q,P$ are polynomials

• $\zeta(2)$: Different ways to prove $\sum_{k=1}^\infty \frac{1}{k^2}=\frac{\pi^2}{6}$ (the Basel problem)

• Divergence of the harmonic series: Why does the series $\sum_{n=1}^\infty\frac1n$ not converge?

• Universal Chord Theorem: Universal Chord Theorem

• Nested radical series: Limit of the nested radical $x_{n+1} = \sqrt{c+x_n}$

• Derivative of a function expressed as $f(x)^{g(x)}$: Differentiation of $x^{\sqrt{x}}$, how?

• Limit of the sequence $\{n^n/n!\}$, is this sequence bounded, convergent and eventually monotonic? ; What's the limit of the sequence $\lim\limits_{n \to\infty} \frac{n!}{n^n}$?

• Single Variable Calculus Reference Recommendations

• Removable discontinuity: How can a function with a hole (removable discontinuity) equal a function with no hole?

• If $f$ is continuous, nonnegative on $[a, b]$, show that $\int_{a}^{b} f(x) d(x) = 0$ iff $f(x) = 0$

Calculus Meets Geometry

• Volume of intersection between cylinders
  • Two cylinders, same radius, orthogonal. This post is not particularly good but there are many existing duplicate-links. Note that this can be done without calculus.
  • Two cylinders variation: different radii (orthogonal), non-orthogonal (same radius), and elliptic cylinders (essentially unsolved).
  • Three cylinders: same radius and orthogonal.

---

Combinatorics combinatorics

• Stars and bars, making change: Counting bounded integer solutions to $\sum_ia_ix_i\leqq n$
• Dice: How many ways can the sum of $n$ dice be $s$?
• Stars and bars with variable upper limits: Extended stars-and-bars problem(where the upper limit of the variable is bounded)
• Password counting: How many ways can you create a password of 10 characters long that has at least one lowercase letter (a-z) and at least one number ($0-9$)?
• Derangements: Number of permutations of $n$ elements where no number $i$ is in position $i$
• Bell numbers, equivalence relations: How many equivalence relations on a set with 4 elements.
• How many ways can N elements be partitioned into subsets of size K?
• Seating arrangements of four men and three women around a circular table
• How many different spanning trees of $K_n \setminus e$ are there? (or Spanning Trees of the Complete Graph minus an edge)

---

Functional equations functional-equations

• Is there a name for function with the exponential property $f(x+y)=f(x) \cdot f(y)$?

---

Geometry geometry

• The "World's Hardest Elementary Geometry Problem": Langley's Adventitious Angles

---

Graph theory graph-theory

How to tell whether two graphs are isomorphic?

---

Group theory group-theory

For a finite group of order $2n$ does there exist $x$ such that $x\ast x=e$?

An element of a group has the same order as its inverse

How to prove $\,{\rm order}(a^k) = n/\gcd(n,k)\,$ for $\,n={\rm order}(a)$?

---

Linear algebra linear-algebra

• Definition of Matrix Multiplication: (Maybe there should just be one canonical one?)
  • Intuition behind Matrix Multiplication
  • What does matrix multiplication have to do with scalar multiplication?
• On the determinant:
  • What's an intuitive way to think about the determinant?
• Determinants of special matrices:
  • Determinant of a rank $1$ update of a scalar matrix, or characteristic polynomial of a rank $1$ matrix
  • How to compute the determinant of a tridiagonal Toeplitz matrix?
• Eigenvectors and Eigenvalues
  • How Do I Compute the Eigenvalues of a Small Matrix?
• Gram-Schmidt Orthogonalization
  • The Need for the Gram-Schmidt Process
• Prove that A + I is invertible if A is nilpotent
  • A generalization for non-commutative rings
• Interpreting the row echelon form of an (augmented) matrix

---

Logic logic

• What is the difference between $\forall x\exists y$ and $\exists y\forall x$?

---

Number Theory elementary-number-theorynumber-theory

• Modular exponentiation by hand ($a^b\bmod c$)

• Universal divisibility rules: Trick to find multiples mentally

• Solving the congruence $x^2\equiv1\pmod n$: Number of solutions of $x^2=1$ in $\mathbb{Z}/n\mathbb{Z}$

• Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$

• Can $\sqrt{n} + \sqrt{m}$ be rational if neither $n,m$ are perfect squares?

• What is the period of the decimal expansion of $\frac mn$?

• When does $p^2$ divide $an^k + bp$?

• Posts related to proving that among any $2n - 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$

• Formula for Hensel's lemma: Hensel lifting square roots $\!\bmod p\,$ to $\!\bmod p^2$

---

Sequences/Series sequences-and-series (also summation summation)

• Geometric Series: Values of $\sum_{n=0}^\infty x^n$ and $\sum_{n=0}^N x^n$

• Summing series of the form $\sum_n (n+1) x^n$: How can I evaluate $\sum_{n=0}^\infty(n+1)x^n$?

• Finding the limit of rational functions at infinity: Finding the limit of $\frac{Q(n)}{P(n)}$ where $Q,P$ are polynomials

• $\zeta(2)$: Different ways to prove $\sum_{k=1}^\infty \frac{1}{k^2}=\frac{\pi^2}{6}$ (the Basel problem)

• Divergence of the harmonic series: Why does the series $\sum_{n=1}^\infty\frac1n$ not converge?

• Limit of the nested radical $x_{n+1} = \sqrt{c+x_n}$

• Limit of exponential sequence and $n$ factorial: Prove that $\lim \limits_{n \to \infty} \frac{x^n}{n!} = 0$, $x \in \Bbb R$.

• To sum $1+2+3+\cdots$ to $-\frac1{12}$

• Recursively defined sequences: Limit of a mean sequence

---

Elementary set theory elementary-set-theory

• The set of all finite subsets / $n$-element subsets / 2-element subsets of $\Bbb N$ is countable

• There are different sizes of infinity: What Does it Really Mean to Have Different Kinds of Infinities?

---

Trigonometry trigonometry

• Solving triangles: Solving Triangles (finding missing sides/angles given 3 sides/angles)

• (Confusing) notation for inverse functions ($\sin^{-1}$ vs. $\arcsin$): $\arcsin$ written as $\sin^{-1}(x)$

• Notation for the square of a trigonometric function (What does $\sin(x)^2$ or $\sin^2$ mean?): What are the meanings of $\operatorname{trig}(x)^n$ and $\operatorname{trig}^n(x)$?

Polynomials polynomials

• How to prove $\,x^a-1 \mid x^b-1 \iff a\mid b$

• Is there a systematic way of solving cubic equations?

Answer 1

Burnside lemma and Pólya enumeration theorem examples

Observe that the convention at the OEIS is that the term necklace refers to the slots being arranged around a circle with rotational symmetry acting on them. Similarly the term bracelet indicates reflections acting on the slots in addition to rotations. This is the difference between the cyclic group $C_n$ acting on $n$ elements (necklace) and the dihedral group $D_n$ on $n$ elements (bracelet).

symmetries of polyhedra

• Coloring the faces of a hypercube
• Burnside's formula on a hexagon
• Coloring the faces of a regular dodecahedron
• Coloring the edges of a regular dodecahedron
• Edge colorings of the cube and Power Group Enumeration
• Put two red, two blue, and two yellow stickers on the faces of a cube
• Coloring the faces of tetrahedra and cubes
• Coloring the faces of a cube with $n$ colors
• Coloring the faces of a cube with exactly $M$ colors by Stirling numbers
• Color the vertices of a regular tetrahedron
• Coloring cube diagonals under rotations and Inclusion-Exclusion
• Proper cube colorings under rotational symmetry and the chromatic polynomial of the octahedron
• Coloring the vertices of the icosahedron
• Coloring vertices and edges of a tetrahedron simultaneously
• Coloring vertices and faces of a cube simultaneously, color count is exact or max
• Coloring the faces of a truncated tetrahedron and a truncated cube
• Coloring the vertices of a cube
• Coloring a snub cube
• Coloring the faces of a truncated octahedron
• Two-colorings of the n-dimensional cube
• Face colorings of the rhombic dodecahedron / edge colorings of the cube
• Simultaneously coloring the faces, vertices and edges of a cube

enumerating types of graphs

• Counting non-isomorphic graphs with self-loops
• Enumerating caterpillar graphs
• Counting non-isomorphic graphs
• Counting non-isomorphic graphs, optimized version
• Counting non-isomorphic graphs, connected graphs
• Nonisomorphic graphs with 4 vertices
• Enumeration of centipede graphs
• Unlabled rooted trees with maximum outdegree
• Unlabled unrooted trees with odd degree sequence
• Counting two types of spanning subgraphs of the complete bipartite graph $K_{n,m}$
• Counting two-colorings of full rooted unordered binary trees (child nodes may be swapped)
• Multigraphs with n labled edges or set partitions of a multiset containing two instances of n distinguishable types of elements
• Algorithm to compute orbital chromatic polynomials
• Enumerating directed graphs
• Digraphs on three vertices

number theory and algebra

• Binary matrices under dihedral symmetry of the square
• Binary Matrices with the symmetric group permuting rows and columns
• Matrices with the symmetric group permuting rows and columns, optimized version
• Matrices with the symmetric group permuting rows and columns, optimized version, worked example
• Partitions without duplicates by the cycle index of the set operator
• Partitions without duplicates by the cycle index of the set operator, recurrence
• Partitions without duplicates by the cycle index of the set operator, closed form for fixed count
• Counting binary structures
• Enumerating cyclic compositions
• Counting non-isomorphic relations
• How many $\{x,y,z\} \subset \{1,2,\ldots, 100\}$ have $x+y+z$ divisible by 3?
• Subsets of size $k$ of $p$ elements whose sum is divisible by $p$
• Probability that a subset of $k$ elements of $[n]$ sums to a multiple of $n$
• Probability that a multiset of $k$ elements drawn from $[n]$ sums to a multiple of $n$
• Generic algorithm for counting subsets of $n$ elements of $\{1,2,\ldots,q\}$ whose sum is divisible by some $k$
• Using the PET on Dirichlet series
• Proving harmonic sum identities by applying PET to finite Dirichlet series
• Counting Abelian groups -- a number-theoretic application of the PET
• Cycle indices of the symmetric and alternating group and the partition function
• The OGF of the cycle indices of the symmetric group and the partition function
• Distributing red, green and blue balls into n indistinguishable bins with no empty bins and no duplicate bin contents, alternatively, factoring into distinct factors of an integer with three prime divisors
• Presence of multiples of some factor $p$ in a random subset of some size $mp$ of an integer range multiple of $mp$
• Connection between the OGF of the unlabeled set operator and the Newton-Girard formulae
• Count of factorizations of an integer $n$ into $k$ distinct factors
• OGF of the unlabeled set operator and a combinatorial sum
• multiplicative partition function, PET and OGF of the cycle index of the symmetric group
• unlabeled set / multiset operator sums, Stirling numbers and the OGF of the cycle index of the symmetric group
• multiplicative partition function on products of primes, PET and OGF of the cycle index of the set operator
• using the exponential formula to factor the polynomial $1-z^n$
• computing a closed form of the cycle index of the symmetric group
• a kind of set cover
• the cycle index of a cyclic group generated by a given permutation
• multisets of multisets with the number of elements in a given range and a repeated element
• subset sum divisible by n and exponential formula

power group enumeration

• Power Group Enumeration with two instances of the symmetric group by Burnside
• Power Group Enumeration of necklaces with swappable colors
• Counting functions $[n]\to[n]$ by Simultaneous Power Group Enumeration
• Power Group Enumeration on coloring the edges of a cube
• Power Group Enumeration of $k$-subsets of the standard deck of $52$ cards wrt. permutation of suits
• Stirling numbers and Power Group Enumeration: EGF
• Stirling numbers and Power Group Enumeration II: OGF
• Counting sets of lottery tickets wrt. permutations of the values by the symmetric group
• Coloring an N by N square with Q interchangeable colors
• Coloring an N by M square wrt row and column permutations by the symmetric group with the column permutations also acting on the colors
• Number of sets of sequences of total length n over an alphabet of n letters with the symmetric group acting on the letters
• Enumerating a type of hexagonal tile
• Equivalence classes of Boolean functions
• Partitioning the multiset [1,1,2,2,...,n,n] into k submultisets

necklaces and bracelets

• Summary sheet on necklaces and bracelets
• Necklace problem variations
• Efficient coefficient extraction for certain necklaces
• Primitive necklaces, the Mobius function, and Power Group Enumeration
• Necklaces with two colors
• Additional bracelet/necklace computation
• A garland of roses with adjacency constraints
• How to convert from PET to Burnside and back on a bracelet example
• Cookbook type explanation of a necklace enumeration
• Two-coloring a necklace on $2n$ beads where opposite beads must have different colors
• Another introductory necklace example
• More necklace computations
• A bracelet of sixteen beads and two colors
• Necklaces with the forbidden pattern 110
• Simultaneous action on vertices and edges of a hexagonal bracelet (dihedral symmetry)
• Primitive necklaces, the general formula, with number-theoretic proof
• Bracelet with two instances of each of N colors.
• Necklaces and bracelets with ten slots
• Necklaces with at most some number of colors where adjacent colors must be different
• Necklaces with two instances of each of n colors where adjacent slots must be different
• Coloring a board with toroidal symmetry
• Necklace / bracelet documented example
• Necklaces from musical notes
• Extracting a closed form for a type of bracelet
• Coloring necklace / bracelet edges and vertices simultaneously
• Necklaces with k colors of beads with n/k beads each
• Coloring bracelets with swappable colors, generating functions
• Coloring bracelets properly, generating functions
• Coloring a twelve-necklace
• Necklaces of n colors with three instances each and no monochrome three-sequence

miscellaneous

• Orbit counting of permutation matrices under rotation
• Introductory commentary on Burnside
• Coloring squares in an $n\times n$ array
• Omitting pieces from a $3×3×3$ array of cubes / stacking constituent cubes
• The ordinary generating function of the cycle index of the symmetric group
• Coloring the edges of a square
• Binary matrices with a fixed number of entries per column under row and column permutations
• Color exactly two squares in a $2n\times 2n$ square array
• Permuting $2^n$ binary numbers by flipping bits, number of functions
• Coloring a triangular array with $n$ levels under rotational symmetry
• Coloring the H-shaped tree
• How many ways to choose three coins of four types?
• 3 Coloring a Baton of n Bands
• Combinatorial problem on bridge deals with spot cards not being distinguishable
• Introductory example
• Polya and Burnside when all of the elements being distributed into the slots must be present at least once and Stirling numbers of the second kind
• Painting the edges of the Petersen graph
• Coloring a 5x5 grid and inclusion-exclusion
• Counting permutations with a given cycle structure
• Coloring a cross-shaped structure embedded in a 5x5 grid and inclusion-exclusion
• Symmetries of the five-by-five square
• Counting multisets of mutisets by multiset cycle indices
• Counting chemical compounds on a hexagonal carbon atom lattice
• Colorings of Kn with an edge removed
• The product of two cycle indices
• Binary n X n X n tensor under rotational symmetry (cube)
• Enumerating orbits
• Placing points on a square grid

Answer 2

More for my own sake than anything else. Integration duplicates tend to be quite hard to find due to the large amount of symbols in titles. Here is a short list of some famous integrals that pop up periodically

Integration integration

• The Gaussian integral: Proving $\int_{0}^{\infty} \mathrm{e}^{-x^2} dx = \dfrac{\sqrt \pi}{2}$. More proofs here.

• The Dirichlet integral: Evaluating the integral $\int_{0}^{\infty} \frac{\sin{x}}{x} \ dx = \frac{\pi}{2}$? This question has many generalizations. See for instance Proof of $\int_0^\infty \left(\frac{\sin x}{x}\right)^2 \mathrm dx=\frac{\pi}{2}.$ or A sine integral $\int_0^{\infty} \left(\frac{\sin x }{x }\right)^n\,\mathrm{d}x$.

• The standard $\int \mathrm{d}x/(1+x^n)$.

  • Definite: How can I compute the integral $\int_{0}^{\infty} \frac{dt}{1+t^4}$?.
  • Indefinite Evaluating $\int \frac{1}{{x^4+1}} dx$.
  • General Indefinite Improper integration involving complex analytic arguments
  • General Indefinite Closed form for $\int_0^\infty {\frac{{{x^n}}}{{1 + {x^m}}}dx }$

• Serret's integral: Evaluate the integral: $\int_{0}^{1} \frac{\ln(x+1)}{x^2+1} \mathrm dx$. See also mathworld for references or Putnam 2005 A5 for further proofs.

• Fresnel integrals: Some way to integrate $\sin(x^2)$? or Evaluating $\int_0^\infty \sin x^2\, dx$ with real methods?. A couple more proofs can be found here.

• The Poisson kernel integral: A question in Complex Analysis $\int_0^{2\pi}\log(1-2r\cos x +r^2)\,dx$

• Wallis integrals: Could not find this question, here is a wikipedia link though.

• The logarithmic sine integral: Computing the integral of $\log(\sin x)$ or Evaluate: $\int_0^{\pi} \ln \left( \sin \theta \right) d\theta$

• Integrals solved by symmetry:

  -- Putnam 1986 5B: A Putnam Integral $\int_2^4 \frac{\sqrt{\ln(9-x)}\,dx}{\sqrt{\ln(9-x)} + \sqrt{\ln(x+3)}}.$

  -- Various forms of $\int_0^{\pi} \frac{\sin^ax \,\mathrm{d}x}{\cos^ax + \sin^ax}$: How to compute $\int_0^{\pi/2}\frac{\sin^3 t}{\sin^3 t+\cos^3 t}dt$?

  -- The $\tan^a(x)$ integral: Integrate $\int_0^{\pi/2} \frac{1}{1+\tan^\alpha{x}}\,\mathrm{d}x$

Answer 3

There ought to be an entry for the calculus / limit classic:

$$\lim_{n\to\infty} \left(1+\frac xn\right)^n = \exp x$$

I found these posts on it so far:

• About $\lim \left(1+\frac {x}{n}\right)^n$
• Intuitive proofs that $\lim\limits_{n\to\infty}\left(1+\frac xn\right)^n=e^x$
• Proving $\lim \limits_{n\to +\infty } \left(1+\frac{x}{n}\right)^n=\text{e}^x$.
• $\lim_{n\rightarrow \infty}(1+\frac{r}{n})^n$ is equal to ${e^{r}}$?
• Why isn't $\lim \limits_{x\to\infty}\left(1+\frac{1}{x}\right)^{x}$ equal to $1$?
• Show that $\lim_{x\to \infty}\left( 1-\frac{\lambda}{x} \right)^x = e^{-\lambda}$

which I've ordered from most to least suited for faq status (after a suitable amount of editing). There are probably more, but I couldn't find them by searching the site.

(I've posted this answer because it is not obvious which one of the above should get faq status.)

Answer 4

Frequent duplicate induction problems

• Partial sum of geometric series

• Sum of binomial coefficients is $2^n$

• $2^n > n^2$

• $n! > 2^n$ for $n \geq 4$

  • $n! > 3^n$ for $n \geq 6$ or maybe this.
  • For $n! > 4^n$ and above, currently there are only isolated posts and not a network to be made.

• If $n>2$, then $n! < n^n$

• If $n>2$, then $(n!)^2>n^n$

• $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ (Maybe there is a better duplicate that focuses more on a proof by induction rather than just any proof--this duplicate may be a good choice, for example)

• Every $n > 1$ can be written as a product of primes

• $n^2 > n$ for all $n \in \mathbb{Z}$

• $1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n+1)^2}{4}$

• Bernoulli's inequality $(1 + x)^n \ge 1 + nx$

Answer 5

Hypergeometric/Summation Identities summation

Rather than have these broken up among algebra-precalculus, proof by induction, combinatorics, etc. I am gathering them all in one place.

---

Faulhaber identities (sums of powers)

$\sum\limits_{k = 1}^n k = \frac{k(k+1)}{2}$ (triangle numbers)

• What is the term for a factorial type operation, but with summation instead of products?
• Proof that $1+2+3+4+\cdots+n = \frac{n\times(n+1)}2$

$\sum\limits_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$ (pyramid numbers)

• How do I come up with a function to count a pyramid of apples?
• Sum of First $n$ Squares Equals $\frac{n(n+1)(2n+1)}{6}$
• How to get to the formula for the sum of squares of first n numbers?
• how can one find the value of the expression, $(1^2+2^2+3^2+\cdots+n^2)$
• How to calculate the sum of $(n-1)^2+(n-2)^2+...+1$?

$\sum\limits_{k=1}^n {k^3} = \left(\sum\limits_{k=1}^n k\right)^2$ (sum of cubes)

• With Induction: Proving $1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ using induction
• Without Induction: Proving the identity $\sum_{k=1}^n {k^3} = \big(\sum_{k=1}^n k\big)^2$ without induction

$\sum\limits_{k=1}^n k^p$ (general formula)

• Finite Sum of Power?
• Methods to compute $\sum_{k=1}^nk^p$ without Faulhaber's formula

---

Geometric series/(Generalized) Binomial Theorem

$\sum\limits_{k=0}^n \binom{n}{k} (-1)^k$

• How to prove that $\sum_{k=0}^{n}(-1)^k \binom {n}{k}=0 $

$\sum\limits_{n = 0}^\infty x^n = \frac{1}{1-x}$ and $\sum\limits_{n = 0}^N x^n = \frac{1 - x^{N + 1}}{1-x}$ (geometric series)

• Values of $\sum_{n=0}^\infty x^n$ and $\sum_{n=0}^N x^n$

$\sum\limits_{n = 0}^\infty (n+1)x^n = \frac{1}{(1-x)^2}$ (derivative of geometric series)

• How can I evaluate $\sum_{n=0}^\infty(n+1)x^n$?

$\sum\limits_{n=0}^{\infty} \binom{n+k}{k} x^n = \frac1{(1-x)^{k + 1}}$ (Negative Binomial Theorem)

• Closed form for $\sum_{n=0}^{\infty} \binom{n+k}{k} x^n$ (Negative Binomial Theorem)

$\sum\limits_{k = 1}^n k \binom{n}{k} = n2^{n-1}$ (derivative of binomial theorem)

• How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$?

---

Vandermonde-like identities

$\sum\limits_{k = 0}^{n} \binom{a}{k} \binom{b}{n - k} = \binom{a + b}{n}$ (Vandermonde's identity)

• How to prove Vandermonde's Identity: $\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$?

$\sum\limits_{k = 0}^{n} (-1)^k\binom{a}{k} \binom{b}{n - k} = \left[x^n\right](1-x)^a(1+x)^b$ (alternating Vandermonde sum)

• Alternating sign Vandermonde convolution

$\sum\limits_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$ (special case of Vandermonde)

• Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$

---

Other

$\sum\limits_{k=0}^{N}\binom{k}{n}=\binom{N+1}{n+1}$ (Hockey-Stick Identity)

• Proof of the hockey stick/Zhu Shijie identity $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$
• Prove $\sum\limits_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity)
• Induction proof concerning a sum of binomial coefficients: $\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$

$\sum\limits_{k=0}^{n}\binom{2k}{k}\binom{2n-2k}{n-k}=4^n$ (convolution of central binomial coefficients)

• Identity for convolution of central binomial coefficients: $\sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$

Answer 6

Probability probability

• "Two Children Puzzle / Boy Born on a Tuesday" and variants:

  • In a family with two children, what are the chances, if one of the children is a girl, that both children are girls?
  • New Two Children problem
  • Boy Born on a Tuesday - is it just a language trick?

• A "liar paradox" variant: Multiple-choice question about the probability of a random answer to itself being correct

• Bertrand's box paradox

• Expectation as tail probability (complementary CDF) integral/sum.

  • Continuous (generalized to any $E[X^p]$ in the answer): Explain why $E(X) = \int_0^\infty (1-F_X (t)) \, dt$ for every nonnegative random variable $X$.

  • Discrete: Find the Mean for Non-Negative Integer-Valued Random Variable

  • Measure-theoretic treatment: Rigorous proof that $\int_{\Omega}X\;dP=\int_{-\infty}^{\infty}xf(x)\;dx$

• Probability for roots of a quadratic equation to be real, where the coefficients are iid random variables with distribution:

  • discrete uniform$\{1,2, 3,4,5,6\}$ from standard die, whereas 322939 is also a good candidate. ^{There are isolated posts regarding discrete uniform of different ranges, and continuous uniform, exponential distribution, etc.}

• Coupon collector's problem coupon-collector

  • standard version
    • expectation: Expected time to roll all $1$ through $6$ on a die (duplicated at calculating expected number of packets.)
    • probability distribution: Probability distribution in the coupon collector's problem
  • only desired items
    • expectation: Coupon collector problem with partial collection of a specific set of coupons (duplicated at Pile of cards - Probability question)
    • probability distribution: Coupon Collector Prob Variation (duplicated at Coupon collector - Chance of collecting desired coupons but not a full set.)
  • batches / groups / packets
    • fixed number per packet, distinct coupons:
      • expectation: Expected number of times a set of 10 integers (selected from 1-100) is selected before all 100 are seen (duplicated at Probability - Expected number of draws to get all 52 cards at least once drawing in groups of size n and Expected number of games so that every player has been an Imposter in Among Us)
      • probability distribution: Sample all elements from a set at least once, with replacement
    • fixed number per packet, repetitions allowed:
      • expectation: Coupon Collector Problem with Batched Selections (duplicated at How to calculate the expected value of the coupon collector problem if we are collecting the coupons in groups of k?)
      • probability distribution: Coupon Collector's problem, version with multiple coupons in a box
    • random number per packet, distinct coupons: coupon collector problem with groups
  • unequal probabilities:
    • mean and variance: Coupon collector's problem: mean and variance in number of coupons to be collected to complete a set (unequal probabilities)
    • probability distribution: Probability that N i.i.d. draws from a multinomial distribution have made all events appear

---

Statistics statistics

• Upper tail inequality for the standard normal distribution:

  • Proof of upper-tail inequality for standard normal distribution,
  • Proof of an estimate for the tail of a normal distribution

• Normal approximation (CLT) for discrete Binomial: ... (to be continued... okay, this task is more complicated than expected)

Answer 7

Questions about [irreducible-polynomials] concerning generic methods:

• Methods to see if a polynomial is irreducible

• How to choose correct strategy for irreducibility testing in $\mathbb{Z}[X]$?

• Checking irreducibility of polynomials over number fields

• Techniques for checking irreducibility over the rationals

• Does irreducibility in $\mathbb Q[X]$ always imply the irreducibility in $\mathbb Z[X]$?

• If $q(X)$ is reducible in $\mathbb Z[X]$, then it's reducible in $\mathbb Z_p[X]$ for every prime $p$

• Does irreducibility in $\mathbb{F}_p[x]$ imply irreducibility in $\mathbb{Q}[x]$?

• Prove that the polynomial $x^nf(1/x)$ with reverted coefficients is also irreducible polynomial over $\mathbb{Q}$

• Motivation for Eisenstein Criterion

• Explaining Newton Polygon for proving irreducibility of polynomial in $\mathbb{Z}[x]$ in elementary way

• When is the polynomial $x^n-a$ irreducible: the result and links, on-site proof in the case $n$ prime.

Answer 8

There are some standard questions in general-topology:

• A continuous bijection from a compact space to a $T_2$ space is always a homeomorphism

• Compact set in a Hausdorff topological space is closed

• Compact set might not be closed in a general topological space

• No continuous bijection between an interval $[0,1]$ and a square $[0,1]^2$

• Continuous image of compact sets are compact

• Compactness of a metric space in terms of their continuous functions: 1, 2

Book recommendations:

• Best book of topology for beginner?
• Can anybody recommend me a topology textbook?
• Choosing a text for a First Course in Topology
• Introductory book on Topology
• Reference for general-topology (Related, but not the same)

Answer 9

A couple of analysis exercises that appear frequently:

• prove that $f'(a)=\lim_{x\rightarrow a}f'(x)$.
• if $f'(x)\rightarrow L$ as $ x \rightarrow \infty$, $-\infty \leq L \leq \infty $ then $ f(x)/x \rightarrow L $ as $x \rightarrow \infty$

Answer 10

Continued Fractions continued-fractions

• Pell Equations:
  • algebra direct connect pell eqn soln $(p_{nk},q_{nk})$ with $(p_n + q_n\sqrt{D})^k$