Conjectures

A conjecture is a mathematical statement that has not yet been rigorously proved. Conjectures arise when one notices a pattern that holds true for many cases. However, just because a pattern holds true for many cases does not mean that the pattern will hold true for all cases. Conjectures must be proved for the mathematical observation to be fully accepted. When a conjecture is rigorously proved, it becomes a theorem.

A conjecture is an important step in problem solving; it is not just a tool for professional mathematicians. In everyday problem solving, it is very rare that a problem's solution is immediately apparent. Instead, the problem solving process involves analyzing the problem structure, examining cases, developing a conjecture about the solution, and then confirming that conjecture through proof.

Conjectures can be made by anyone, as long as one notices a consistent pattern. Consider the following example involving Pascal's triangle:

The $0^\text{th}$ through $4^\text{th}$ rows of Pascal's triangle are shown below.

$$1\\ 1\quad 1\\ 1\quad 2 \quad 1\\ 1\quad 3 \quad 3 \quad 1\\ 1\quad 4 \quad 6 \quad 4 \quad 1\\ \cdots$$

Conjecture an expression for the sum of the elements in the $n^\text{th}$ row of Pascal's triangle.

---

The most sensible approach to begin the process of conjecturing is to see what happens for simple cases. Start by summing the first couple of rows:

$$\begin{array}{lrcl} 0^\text{th}\text{ row:} & 1 & = & 1 \\ 1^\text{st}\text{ row:} & 1+1 & = & 2 \\ 2^\text{nd}\text{ row:} & 1+2+1 & = & 4 \\ 3^\text{rd}\text{ row:} & 1+3+3+1 & = & 8 \\ 4^\text{th}\text{ row:} & 1+4+6+4+1 & = & 16. \end{array}$$

Now, observe the pattern in these results. It is clear that these are powers of $2$. Try the next row to see if the pattern holds (recall how to construct the rows of Pascal's triangle):

$$\begin{array}{lrcl} 5^\text{th}\text{ row:} & 1+5+10+10+5+1 & = & 32. \\ \end{array}$$

The pattern seems to hold. One can try as many rows as one would like, but the information gathered so far is enough to make a conjecture.

Conjecture: The sum of the elements in the $n^\text{th}$ row of Pascal's triangle is $2^n$. $_\square$

Some conjectures can be more elusive to develop. If the pattern isn't obvious, carefully observe how the problem is structured.

Observe the following pattern:

Let $x_n$ be the number of segments that connect an $n\times n$ square lattice. Conjecture an expression for $x_n$.

---

Observing the cases given by counting how many segments are in each figure, we have

$$\begin{aligned} x_0 &= 0 \\ x_1 &= 4 \\ x_2 &= 12. \end{aligned}$$

From these three cases, no obvious pattern emerges. Observe what the next case looks like:

Counting the segments here gives $x_3=24$. One might notice that each difference between consecutive terms in the sequence is a multiple of 4:

$$\begin{aligned} x_1-x_0 &= 4 \\ x_2-x_1 &= 8 \\ x_3-x_2 &= 12. \end{aligned}$$

This observation could lead one to write a recurrence relation

$$x_n=x_{n-1}+4n.$$

However, this would become a very tedious calculation if one was required to find the $100^\text{th}$ term in the sequence. It would be more desirable to develop an expression for $x_n$ purely in terms of $n$.

One could attempt to observe more cases in the sequence to see if any numerical pattern emerges. Often, a better way to tackle these kinds of problems is to think more creatively about how the problem is structured. Observe the same case for $n=3$, except now the horizontal and vertical segments are color-coded.

Notice that there are $4$ horizontal lengths (in red), and each of them consists of $3$ segments. The same is true for vertical lengths (in blue). Written as an expression, the total number of segments is

$$x_3=2(3)(4)=24.$$

Now consider the other cases, and see if the same structure applies:

$$\begin{array}{ccccc} x_0 & = & 2(0)(1) & = & 0 \\ x_1 & = & 2(1)(2) & = & 4 \\ x_2 & = & 2(2)(3) & = & 12. \end{array}$$

The pattern appears to hold. This gives enough information to write a conjecture.

Conjecture: The number of segments connecting an $n\times n$ lattice is defined by the sequence $x_n=2n(n+1)$. $_\square$

Keep in mind that observing a conjecture to be true for many cases doesn't make it true for all cases. In the history of mathematics, there have been many conjectures that were shown to be true for many cases, but were eventually disproved by a counterexample. For the sake of problem solving, it's important to prove each of these conjectures to ensure that they are correct.

One must always be wary of falling into the trap of observing a pattern and believing it must hold true for all cases. Consider the following values of the partition function:

$$\begin{aligned} p(2) &= 2 \\ p(3) &= 3 \\ p(4) &= 5 \\ p(5) &= 7 \\ p(6) &= 11. \end{aligned}$$

There is a very tempting pattern within these values, and it might cause one to make the following conjecture:

(Incorrect) Conjecture: The number of partitions of an integer $n$ is $p_{n-1}$, where $p_k$ is the $k^\text{th}$ prime number.

Observing the very next value of $p(n)$ puts this conjecture to rest: $p(7)=15$. As soon as a single case is shown to disobey the pattern, the conjecture is disproved. This is called a counterexample. Once a counterexample is found, it's not necessary to check any more values of the partition function. A conjecture must hold true for all cases, not just some.

Disproving a conjecture by counterexample can ensure that one isn't wasting time chasing a pattern that doesn't exist. However easy it is to disprove conjectures, a method to prove conjectures is still required.

The most common method for proving conjectures is direct proof. This method will be used to prove the lattice problem above.

Prove that the number of segments connecting an $n\times n$ lattice is $2n(n+1)$.

---

Recall from the previous example how the segments in the lattice were counted. Most of work for the proof is already completed. Writing the proof is merely a process of formalizing how the formula was obtained.

Proof: In each $n\times n$ lattice, there are $n+1$ horizontal lengths, each consisting of $n$ segments. This is likewise true for vertical lengths. Thus, the total number of segments connecting an $n\times n$ lattice is $2n(n+1)$. $_\square$

Another possible method of proof is induction. Induction is most useful when the different cases in a problem are related to each other. As the elements of Pascal's triangle are very closely related to each other, this method is very useful for proofs involving Pascal's triangle.

Prove that the sum of the elements in the $n^\text{th}$ row of Pascal's triangle is $2^n$.

---

Let $s(n)$ be the sum of the elements in the $n^\text{th}$ row of Pascal's triangle.

Base Case: The $0^\text{th}$ row contains only $1$. Therefore, $s(n)=1=2^0$.

Inductive Step: Assume that $s(n)=2^n$ for some integer $n$. Show that if $s(n)=2^n$, then $s(n+1)=2^{n+1}$.

This step requires some thinking about how the rows are related to each other. It might not be immediately apparent how this can be done, so begin with a single case. Examine how the $3^\text{rd}$ and $4^\text{th}$ rows are related to each other:

$$\begin{array}{rc} 3^\text{rd}\text{ row: } & 1 \quad 3 \quad 3 \quad 1 \\ 4^\text{th}\text{ row: } & 1 \quad 4 \quad 6 \quad 4 \quad 1. \end{array}$$

The elements in the $4^\text{th}$ row are composed of sums of elements in the $3^\text{rd}$ row:

$$\begin{array}{rc} 3^\text{rd}\text{ row: } & \color{#D61F06}{1} \qquad \quad \color{#3D99F6}{3} \qquad \quad \color{#20A900}{3} \qquad \quad \color{#69047E}{1} \\ 4^\text{th}\text{ row: } & \color{#D61F06}{1} \qquad \color{#D61F06}{1}+\color{#3D99F6}{3} \quad \color{#3D99F6}{3}+\color{#20A900}{3} \quad \color{#20A900}{3}+\color{#69047E}{1} \qquad \color{#69047E}{1}. \end{array}$$

Each element in the $3^\text{rd}$ row appears exactly twice in the sums which compose the $4^\text{th}$ row. Thus, the sum of elements in the $4^\text{th}$ row is exactly twice as much as sum of elements in the $3^\text{rd}$ row. Elements in Pascal's triangle are always composed of sums of elements from the preceding row. Thus, $s(n+1)=2s(n)$ for any positive integer $n$.

If $s(n)=2^n$, then $s(n+1)=2\times 2^n=2^{n+1}$. The inductive step is complete. Thus, the sum of elements in the $n^\text{th}$ row of Pascal's triangle is $2^n$. $_\square$

Still another method for proving conjectures is to establish a bijection. Sometimes, other mathematicians have done the bulk of work required to solve a problem. What remains is to make the connection between other mathematicians' work and this problem, to apply formulas and theorems correctly.

Ann stands on the Southwest corner of the figure below. The lines represent streets.

If Ann only travels North or East along the streets, how many paths will take her to the school in the Northeast corner?

Generalize this problem for an $m\times n$ grid.

---

It may not seem immediately clear how to approach this problem. A good start would be to examine a couple of cases to see if a pattern emerges.

One possible path for Ann would be to travel all the way North and then all the way East.

$$\text{Path: NNNEEEE}$$

Another possible path would be to travel all the way East and then all the way North.

$$\text{Path: EEEENNN}$$

It's also possible to alternate between traveling North and East.

$$\text{Path: EENENEN}$$

One could continue exhaustively listing out all the possible paths. As the paths are listed out, attempt to look for patterns or common threads.

Notice how each path consists of exactly $7$ moves, $3$ of which are North moves and $4$ of which are East moves. What makes a path distinct is in what order those moves occur. This information can be used to establish a bijection.

Consider the order of Ann's moves to be defined as an order of $7$ moves, $3$ of which are North moves, with the rest being East moves. Ann's path can be defined as a combination of $7$ moves, $3$ of which are North. Thus, the paths that Ann could possibly take have a bijective relationship with the combinations of $3$ distinct objects out of $7$.

The number of combinations can be calculated with the binomial coefficient

$$\binom{7}{3}=35.$$

Thus, there are $35$ possible paths that Ann could take.

More generally, the number of paths leading from one corner of an $m\times n$ grid to the opposite corner is $\binom{m+n}{n}$. This problem is explored further in the rectangular grid walk page. $_\square$

There are many open conjectures in mathematics. An open conjecture is one that has been proposed, but no formal proof has yet been developed. The conjectures below are some of the most famous open conjectures.

Goldbach's Conjecture: (proposed 1742 by Christian Goldbach)

Every even integer greater than $2$ can be expressed as the sum of two (not necessarily distinct) prime numbers.

One can observe Goldbach's Conjecture for small cases:

$$\begin{aligned} 4 &= 2+2 \\ 6 &= 3+3 \\ 8 &= 3+5 \\ 10 &= 5+5 \\ 12 &= 5+7 \\ 14 &= 7+7 \\ 16 &= 3+13 \\ 18 &= 7+11 \\ &\cdots \end{aligned}$$

This process of checking all even numbers can be continued for a very long time. With the aid of computers, mathematicians have found that all even numbers up to $4\times 10^{18}$ can be expressed as the sum of two prime numbers. Even though Goldbach's Conjecture holds for numbers so large, no mathematician has been able to prove that this pattern extends to infinity. If an even number that cannot be expressed as the sum of two primes were to be found, it would be very surprising.

Twin Prime Conjecture: (proposed 1849 by by Alphonse de Polignac)

There are infinitely many pairs of twin primes.

It has been known for a very long time that there are infinitely many prime numbers. Twin primes, primes that differ by $2$, are somewhat exceptional because primes are typically spaced far apart. The first couple of twin prime pairs are $(3,5)$, $(5,7)$, and $(11,13)$. Larger and larger pairs of twin primes continue to be discovered; as of September 2016, the largest known twin prime pair is $2996863034895\times 2^{1290000}\pm 1$.

Recently, mathematicians Yitang Zhang and Terence Tao have produced work that suggests an upper bound for which there are infinitely many primes that differ by at most that amount. As of this writing, this upper bound is 246.

Riemann Hypothesis: (proposed 1859 by Bernhard Riemann)

The Riemann zeta function has its zeros only at the negative even integers and the complex numbers with real part $\frac{1}{2}$.

The Riemann hypothesis is one of the most important open problems in mathematics. If it were to be proved, it would lead to several important developments in number theory and algebra. The most notable of these potential developments would be a better understanding of the distribution of primes.

$abc$ Conjecture: (proposed 1985 by Joseph Osterlé and David Masser)

Let $a$, $b$, and $c$ be positive pairwise co-prime integers such that $a+b=c$. Let $d$ be the product of the distinct prime factors of $abc$. The $abc$ conjecture states that $d$ is usually not much smaller than $c$.

The actual statement of the $abc$ conjecture is much more precise and well-defined than the language, "usually not much smaller," used here. However, this will suffice to demonstrate an example. The language implies that $d$ is typically larger than $c$, and only in extreme rare cases is $d$ much smaller than $c$.

Let $a=49$, $b=75$, and $c=a+b$. Let $d$ be the product of distinct prime factors of $abc$. Show that $d>c$.

---

We have

$$\begin{aligned} a&=7^2\\ b&=3\times 5^2\\\\ c&=a+b=49+75\\ &=124\\ &=2^2\times 31. \end{aligned}$$

Note that $\gcd(a,b)=1$, $\gcd(a,c)=1$, and $\gcd(b,c)=1$. This establishes that $a$, $b$, and $c$ are pairwise co-prime, which is an important requirement of the $abc$ conjecture.

The distinct prime factors of $abc$ are $2$, $3$, $5$, $7$, and $31$. The product of these factors is then

$$d=2\times 3\times 5\times 7\times 31=6510.$$

Thus, $d>c$. $_\square$

If one were to test many triplets $(a,b,c)$ that meet the requirements of the $abc$ conjecture, one would find very few in which $d<c$. The smallest possible triplet for which this is the case is $(1,8,9)$. The University of Leiden has led a search of triplets in which $d<c$.

The $abc$ conjecture is especially notable on this list because a proof is pending. In 2012, Shinichi Mochizuki published a series of new findings, including a proof of the $abc$ conjecture. These new findings are, as of this writing, being reviewed by the mathematical community to ensure their accuracy. If this proof were to be accepted, then it would lead to an explosion of new theorems in number theory.

Although the above conjectures are still open, some conjectures have been open for a very long time, only to be recently proved. Below are a couple of the most famous examples.

Fermat's Last Theorem: (proposed 1637 by Pierre de Fermat, proved 1994 by Andrew Wiles)

$$a^n+b^n=c^n$$

There are no integer solutions $(a,\ b,\ c)$ for the above equation for any integer $n>2$. $_\square$

Fermat's last theorem, originally written in the margins of Pierre de Fermat's copy of Arithmetica in 1637, frustrated mathematicians for centuries. During this time, many formal proofs were attempted, but none were successful. It wasn't until 1994 that Andrew Wiles released a formal proof that was accepted by the mathematical community.

Four Color Theorem: (proposed ~1850, proved 1976 by Kenneth Appel and Wolfgang Haken)

Given any separation of a plane into contiguous regions, only four colors are needed to color the regions such that no pair of adjacent regions are the same color. $_\square$

Image Credit: Wikipedia

The four color theorem is of particular interest because of how it was proved. It was the first major mathematical theorem to be proved with the help of computers. Appel and Haken's approach involved mapping out a set of possible counterexamples, and using these possible counterexamples to show that no counterexample could exist. If no counterexample could exist, then the theorem must be true. Their proof would have required an extremely extensive analysis by hand, but computers allowed this analysis to be done with much less effort.

Poincaré Conjecture: (proposed 1904 by Henri Poincaré, proved 2002 by Grigori Perelman)

Every simply connected, closed 3-manifold is homeomorphic to the 3-sphere.

The Poincaré conjecture has been so recently proved that it is still popularly known as a conjecture rather than as the "Poincaré theorem." The wiki page linked here contains much more information and explanations about the theorem.

In some rare cases, a conjecture with strong evidence has been proposed, only to be disproved some time later. There are also some mathematical observations which strongly suggest a pattern, but this pattern does not hold for all cases. Below are a couple of examples.

Prime-Generating Function:

A prime-generating function produces prime number outputs for a specified set of inputs. As of now, there is no known prime-generating function that can be efficiently computed.

Even though no known prime-generating functions exist, there are many examples of functions that seem to come close.

Euler's Prime-Generating Polynomial:

We have

$$f(n)=n^2+n+41.$$

For non-negative integer values of $n$ less than $41$, $f(n)$ is a prime number:

$$\begin{aligned} f(0) &= 41 \\ f(1) &= 43 \\ f(2) &= 47 \\ f(3) &= 53 \\ \vdots \\ f(40) &= 1681. \end{aligned}$$

Note that $f(41)$ is certain to be a composite number:

$$\begin{aligned} f(41) &= 41^2+41+41 \\ f(41) &= 41(41+1+1) \\ f(41) &= 41(43). \end{aligned}$$

Of course, Euler never seriously thought that he had found a prime-generating function. However, an inattentive observer, seeing the first 40 results, might believe that the function would continue to produce primes indefinitely.

Euler produced an astounding amount of important mathematical results in his lifetime. It is somewhat surprising that one of his conjectures turned out to be false.

Euler's Sum of Powers Conjecture: (proposed 1769 by Leonhard Euler, disproved 1966 by L.J. Lander and T.R. Parkin)

Given $n>1$ and $a_1, a_2, \ldots, a_n, b$ are non-zero integers, if

$$\sum\limits_{i=1}^n{a_i^k}=b^k,$$

then $n\ge k$.

Lander and Parkin found a counterexample with $n=4$ and $k=5$, which disproved this conjecture:

$$27^5 + 84^5 + 110^5 + 133^5 = 144^5.$$