Tag: proof

Elegance and Regret

Olly / / Math Posts

I didn’t do any trigonometry today, but instead read more of Steven Strogatz’s The Joy of X and worked on the propositions about digit sums that I found in my notebook.

The most interesting tidbit from The Joy of X was Strogatz’s comment regarding a particular proof of the Pythagorean Theorem that, “The proof does far more than convince; it illuminates. That’s what makes it elegant.” That caught my attention and had me wondering whether all elegant proofs must be illuminating. I haven’t come to a conclusion yet.

To be illuminating is certainly not the only requirement for an elegant proof. The main proposition I worked on today was “the sum of the digits of any multiple of 9 is also a multiple of 9.” I came up with the outline of a proof by induction, the meat of which was a description of what happens to the digit sum when you add 9 to any natural number. It was full of cases and loops and was decidedly not elegant. I do think it gave a good sense of what was happening, though, and it could have been reworked to prove the general theorem that, in base $n$, the digit sum of any multiple of $n-1$ is also a multiple of $n-1$.

I was sure there must be a better proof, however, and I ended up searching for guidance on the Internet. I regret that, as I would rather have discovered the answer I found for myself. I did get to generalize it, at least, since it applied only to two-digit numbers. I’m not sure I would say that the result is illuminating. I don’t think it reveals why the theorem is true, except in as much as “why” is that 9 is one less than the base of the number system being used. It is simple, though. Does that make it elegant?

Proposition: For all $n\in\mathbb{N}$, the digit sum of $9n$ is a multiple of 9.

When $n$ is a natural number, $9n = 10^md_m+10^{m-1}d_{m-1}+…+10d_1+d_0$, where $d_m, d_{m-1},…,d_1, d_0$ are the digits of $9n$, in order.

$$10^md_m+10^{m-1}d_{m-1}+…+10d_1+d_0=$$ $$\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]+\left[d_m+d_{m-1}+…+d_1+d_0\right]$$

Thus, $$d_m+d_{m-1}+…+d_1+d_0=9n-\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]\text{.}$$

Note that the left-hand side of the equation is the digit sum of $9n$.

Note also that, for any natural number $x$, $$10^x-1=\sum_{i=0}^{x-1}10^i(9)=9\sum_{i=0}^{x-1}10^i\text{.}$$

[For instance, $10^3-1=1000-1=999=9(111)$.]

Hence, because each term of the expression is a multiple of 9, $$9n-\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]=9p$$ for some integer $p$.

It follows that the digit sum of $9n$ is a multiple of 9 for all $n\in\mathbb{N}$.

This proof could also be rewritten to cover all bases. In addition, the same argument could be used to prove that, in base 10, the digit sum of any multiple of three is also a multiple of three.

(And it occurs to me as I write this that you could also use it to prove the analogous fact, in base $n$, for any factor of $n-1$. That’s very cool and makes me feel like I have come up with something worthwhile on my own today.)

Conic Completion Day

Olly / / Math Posts

Today I worked through poor concentration to finish the exercises from the review of conics. There wasn’t much left to do, in fact, because the five final exercises all called for tools from calculus that I have not reviewed yet.

Next up will be trigonometry. I didn’t start reading the appendix on that topic today, but I looked over it. I also did a little review of the Unit Circle (which, oddly, isn’t pictured in the review of trigonometry). I remember Mike, my high school math teacher for two out of three years, was very strong on the Unit Circle. He used to say that if he ever met us again as adults, his first question would be, “What’s $\sin\left(\frac{\pi}{6}\right)$?” I did remember the answer to that before my review today, so perhaps threatening years-late pop quizzes is an effective teaching technique.

I reckon it’s about time I present my hand-waving argument that repeating decimals must represent rational numbers. I proved the converse in my post Rational-a-Rama with what I think most of my audience found a boring amount of rigor. Here I’m going to err far on the other side.

Consider the repeating decimal $x=0.\overline{142857}$.

Since $x$ repeats every six digits, multiplying $x$ by $10^6$ will yield another number with the same decimal part: $10^6x=142857.\overline{142857}$

Observe that $10^6x-x=142857.\overline{142857}-0.\overline{142857}=142857$.

Thus $(10^6-1)x=142857$ and $x=\frac{142857}{10^6-1}=\frac{142857}{999999}\text{.}$

Both $142857$ and $999999$ are integers, so it follows that $x=0.\overline{142857}$ is rational.

(In fact, $x=0.\overline{142857}=\frac{142857}{999999}=\frac{1}{7}$.)

A similar argument can be made about any repeating decimal, so any repeating decimal represents a rational number.

(Note that some repeating decimals do not begin repeating right after the decimal point. An example is $y=0.58\overline{3}$ (which is $\frac{7}{12}$). Multiplying $y$ by ten and subtracting $y$ from the result yields $10y-y=5.83\overline{3}-0.58\overline{3}=5.25$. This is not an integer, but it can be made one by multiplying by 100. This leaves the equation $100(10y-y)=525$, which can be used to show that $y$ is rational in the same manner as above.)

Rational-a-Rama

Olly / / Math Posts

Today I will be sharing my proof that the decimal representations of rational numbers must repeat. This proof is based on a simple idea, but turned out to be pretty involved, with several parts.

The fundamental idea can be illustrated using long division. Consider the rational number $\frac{8}{7}$. We can find its decimal representation using the long division calculation below.

Long Division Remainders

Each step of this calculation begins with the remainder from the previous step (circled in red). Since the remainder on division by 7 must be an integer between 0 and 6, there are only 7 possible remainders. Thus, the remainder must repeat within no more than 8 steps. Once it repeats, the calculation will begin to cycle, causing the decimal representation it produces to repeat, as this one does.

Now let’s prepare for the more formal proof by proving two lemmas. I think the first of these is quite interesting and not immediately obvious. The second one is obvious, but I wanted to be assured of it, since it is vital to the main proof.

Lemma 1: Given a rational number $x$, if there exist two distinct digits $d_1$ and $d_2$ in the decimal representation of $x$ such that the sequence of digits following $d_1$ is the same as the sequence of digits following $d_2$, then the decimal representation of $x$ repeats.

Assume that two such digits exist and let the one which appears first be called $d_1$. Then the decimal representation of $x$ begins as follows: $s_1.s_2d_1s_3d_2$, where $s_1$ is a sequence of at least one digit and $s_2$ and $s_3$ are sequences of zero or more digits.

Now, since the sequence of digits following $d_2$ is the same as the sequence of digits following $d_1$, the decimal representation must continue: $s_1.s_2d_1s_3d_2s_3d_2$. Yet this further specifies the sequence of digits following $d_1$, so the same digits must appear again in the sequence following the initial appearance of $d_2$, yielding $s_1.s_2d_1s_3d_2s_3d_2s_3d_2$. This process (illustrated below) will continue infinitely, so $x=s_1.s_2d_1\overline{s_3d_2}$.

Thus, the lemma holds.

Two Digits With Sequences

(I realize the notation was a little sloppy here, with $d_2$ representing both a digit and a digit with its position, but I couldn’t find a good way to fix it.)

Lemma 2: Let $x$ be a non-negative rational number such that $x=\frac{n}{m}$, where $n$ and $m$ are non-negative integers and $m\neq 0$. There is no more than one way to represent $x$ as a mixed number $q\frac{r}{m}$ such that $q$ and $r$ are non-negative integers and $r<m$.

Suppose $\frac{n}{m}=q_1\frac{r_1}{m}$ and $\frac{n}{m}=q_2\frac{r_2}{m}$ where $q_1$, $q_2$, $r_1$, and $r_2$ are non-negative integers and $r_1,r_2<m$.

It follows that $q_1+\frac{r_1}{m}=q_2+\frac{r_2}{m}$ and thence that $q_1-q_2=\frac{r_1-r_2}{m}$.

Since $0<r_1<m$ and $0<r_2<m$, $-1<\frac{r_1-r_2}{m}<1$.

Thus $-1<q_1-q_2<1$, from which it follows that $q_1=q_2$, since $q_1$ and $q_2$ are integers.

Hence $\frac{r_1-r_2}{m}=0$, so $r_1=r_2$.

Therefore, both mixed numbers are the same, and the theorem holds.

Finally, we come to the main theorem.

Proposition: If $x$ is a rational number, then the decimal representation of $x$ repeats.

For any $x$, if the decimal representation of $x$ repeats, then the decimal representation of $-x$ repeats. Thus, it is sufficient to show that the theorem holds for all non-negative $x$.

Let $x$ be a non-negative rational number. Then $x=\frac{n}{m}$ for some non-negative integers $n$ and $m$, where $m\neq 0$.

The fraction $\frac{n}{m}$ can be expressed as a mixed number $q_1\frac{r_1}{m}$ such that $q_1$ and $r_1$ are non-negative integers and $r_1<m$. By Lemma 2, there is only one way to do this.

Using algebra we have: $$q_1\frac{r_1}{m}=q_1+\frac{r_1}{m}=q_1+\frac{r_1}{m}\left(\frac{10}{10}\right)=q_1+\frac{10r_1}{m}\left(\frac{1}{10}\right)$$

As above, the fraction $\frac{10r_1}{m}$ can be expressed uniquely as a mixed number $q_2\frac{r_2}{m}$ such that $q_2$ and $r_2$ are non-negative integers and $r_2<m$.

This yields $$q_1+\frac{10r_1}{m}\left(\frac{1}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)\text{.}$$

Notice that $q_2$ has only one digit, since $0\leq\frac{r_1}{m}<1$ and $0\leq q_2\leq\frac{10r_1}{m}$. Notice also that $0\leq\frac{r_2}{m}\left(\frac{1}{10}\right)<\frac{1}{10}$, since $0\leq\frac{r_2}{m}<1$. This means that $q_2$ is the tenths-place digit of the decimal expansion of $x$.

The algorithm can be continued as shown below, $$q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)\left(\frac{10}{10}\right)$$ $$=q_1+q_2\left(\frac{1}{10}\right)+\frac{10r_2}{m}\left(\frac{1}{100}\right)=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+\frac{r_3}{m}\left(\frac{1}{100}\right)$$ $$=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+\frac{r_3}{m}\left(\frac{1}{100}\right)\left(\frac{10}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+q_4\left(\frac{1}{1000}\right)+\frac{r_4}{m}\left(\frac{1}{1000}\right)…$$ with $q_i\frac{r_i}{m}$ for $i>1$ always the unique mixed number representation of the fraction $\frac{10r_{i-1}}{m}$ such that $q_i$ and $r_i$ are non-negative integers and $r_i<m$. By logic similar to that above, when $i>1$, $q_i$ will always be a digit of the decimal representation of $x$, with its value given by the power of $\frac{1}{10}$ by which it is multiplied.

Since, for all $i$, $r_i$ is a non-negative integer less than $m$, there are only $m$ possible values of $r_i$. This means that, among the infinite values of $r_i$, there must exist distinct $r_j$ and $r_k$ such that $r_j=r_k$. (ETA: By the Pigeonhole Principle!)

Since the mixed number representations used by the algorithm are unique, if $r_j=r_k$, then $q_{j+1}=q_{k+1}$ and $r_{j+1}=r_{k+1}$. By induction, it therefore follows that $q_{j+h}=q_{k+h}$ for all $h$. Since, when $i>1$, each $q_i$ is a digit of the decimal representation of $x$, it follows by Lemma 1 that decimal representation of $x$ repeats.

Therefore the theorem holds.

I hope this makes some measure of sense. I had a lot of trouble making this proof lucid, and eventually I had spent too much time working on. Those whose eyes did not glaze over will note that the algorithm I employed here is essentially long division. In developing it, I did not set out specifically to reproduce the long division algorithm, and I was intrigued when I noticed they are basically the same. Here is our long division problem annotated to show the relationship:

Long Division

Revenge of the Squares, Part 2

Olly / / Math Posts

Today I finished the 46 exercises from the review of analytic geometry, then rounded out my study time with more exercises from Analysis with an Introduction to Proof.

I had expected the proof from Revenge of the Squares, Part 1 to require showing that the figure must be a parallelogram. I managed it without that, but afterward I started thinking about how I would have proved that fact, had I needed it. The results are below.

Lemma: If, when two lines are intersected by another line, a pair of alternate interior angels is equal, then the first two lines are parallel.

Assume that two lines, $A$ and $B$, are not parallel.

Let them both be intersected by a third line, $C$. Since $A$ and $B$ are not parallel, they intersect, and $A$, $B$, and $C$ enclose a triangle.

Three Lines

Let $x$, $y$, and $z$ be the interior angles of the triangle, as shown in the diagram. Let the interior angle alternate to $x$ be called $k$ and the interior angle alternate to $y$ be called $j$.

Since the sum of the measures of the interior angles of a triangle is 180 degrees, $x+y+z=180$. Thus, $x=180-y-z$.

Furthermore, since $x$ and $j$ are complimentary supplementary, $x+j=180$, meaning that $x=180-j$.

Therefore, $$180-j=180-y-z$$ $$-j=-y-z$$ $$j=y+z$$

Since $z\neq 0$, it follows that $j\neq y$.

By similar reasoning, $k\neq x$.

Hence, if two lines are not parallel, then, when they are both intersected by a third line, neither pair of alternate interior angles is equal.

By contrapostition, it follows that if, when two lines are intersected by another line, a pair of alternate interior angels is equal, then the first two lines are parallel.

Proposition: A convex quadrilateral with each pair of opposite sides equal is a parallelogram (i.e. each pair of opposite sides is also parallel).

Consider a convex quadrilateral $ABCD$, where $AB=CD$ and $BC=AD$.

Parallelogram Before
Parellelogram After

Draw $\overline{BD}$.

Since $AB=CD$, $BC=AD$, and $\overline{BD}$ is shared, $\triangle ABD\cong\triangle BCD$ by the side-side-side property.

Therefore, $\angle CBD\cong\angle ADB$ and $\angle BDC\cong\angle ABD$.

It follows, by the lemma, that $\overline{AB}\parallel\overline{CD}$ and $\overline{AD}\parallel\overline{BC}$.

Thus, $ABCD$ is a parallelogram.

SSS again. Proving that remains on the to-do list.

Revenge of the Squares, Part 1

Olly / / Math Posts

I intended to split my study time today between analytic geometry review and logic review, but ended up getting drawn into some exploration as well. The result is that I have two proofs about quadrilaterals ready to post. The first of the two appears below. It’s a proof of my hunch from the post Squares Again that if a convex, four-sided, equilateral polygon has one right angle, then it has four right angles. It turns out that I could prove this without knowing that such a figure must be a parallelogram. (It must, though. That’s the proof for tomorrow.)

Lemma: The angles opposite (i.e. subtended by) the equal sides of an isosceles triangle are also equal.

Triangle Before 1
Triangle After

Consider the isosceles triangle $\triangle ABC$ with $AB=AC$.

Draw a line bisecting $\angle CAB$ and extend it to intersect $\overline{BC}$. Let the point of intersection be called $D$.

Now, by the side-angle-side property, $\triangle ACD\cong\triangle ABD$, since $AB=AC$, $\angle CAD\cong\angle BAD$, and $\overline{AD}$ is shared.

Therefore, $\angle ACD\cong\angle ABD$. These are the angles opposite the equal sides of the original isosceles triangle, so the lemma is proven.

Proposition: If a convex, four-sided, equilateral polygon has one (interior) right angle, then it has four (interior) right angles.

Let $ABCD$ be an convex, four-sided, equilateral polygon, and let $\angle BCD$ be a right angle.

Square Before
Square After

Divide the polygon by drawing $\overline{BD}$.

Note that, since $\overline{BD}$ is shared and all other line segments are equal, $\triangle ABD\cong\triangle BCD$ by the side-side-side property.

Hence, since $\angle BCD$ is a right angle and the angles of congruent triangles are equal, $\angle BAD$ is also a right angle.

Similarly, $\angle ADB\cong\angle CBD$.

Furthermore, by the lemma, since $\triangle ABD$ is isosceles, $\angle ADB\cong\angle ABD$, and since $\triangle ACD$ is isosceles, $\angle BDC\cong\angle CBD$.

Therefore, $\angle ADB\cong\angle ABD\cong\angle BDC\cong\angle CBD$.

Let the measure of those angles be called $x$. Since the sum of the measures of the angles of a triangle is 180 degrees, either triangle gives us the relationship $90+2x=180$, so $x=45$.

The measures of $\angle ADC$ and $\angle ABC$ are both $2x=2(45)=90$. Thus they are also right angles.

Hence, if a convex, four-sided, equilateral polygon has one right angle, then it has four right angles.

This proof uses SSS again—I actually thought of it while trying to work out a proof of SSS—as well as SAS, through the lemma1. It also uses the fact that the measures of the angles of a triangle sum to 180 degrees. I’m pretty sure that theorem is only a couple of steps from the parallel postulate, though.

My original version of this proof didn’t make use of the lemma about isosceles triangles, but instead argued that the two congruent triangles could be mapped onto each other by either rotation or reflection, and that was why all of the acute angles had to be equal. That was kind of a nifty argument, but not easy to formalize.

Stay tuned tomorrow for the proof about parallelograms.

  1. To do. ↩︎

Perpendicular Lines

Olly / / Math Posts

Today I spent all my study time on exploration and proofs, as opposed review exercises. My first goal was to prove Theorem 2 from yesterday:

Two lines with slopes $m_1$ and $m_2$ are perpendicular if and only if $m_1m_2=-1$; that is, their slopes are negative reciprocals:$$m_2=-\frac{1}{m_1}$$

I succeeded in that, and also came up with an argument for the converse of the Pythagorean Theorem, which is needed for the proof.

Argument for the converse of the Pythagorean Theorem

Proposition: Given a triangle with side lengths $a$, $b$, and $c$, if $a^2+b^2=c^2$, then the triangle is a right triangle.

Congruent Triangles

Let $\triangle ABC$ be a triangle such that $CA=\sqrt{AB^2+BC^2}$.

Construct a right triangle $\triangle EFG$ such that $EF=AB$ and $FG=BC$.

By the Pythegorean Theorem, $GE=\sqrt{EF^2+FG^2}$. Furthermore, $\sqrt{EF^2+FG^2}=\sqrt{AB^2+BC^2}=AC$.

Thus, $EF=AB$, $FG=BC$, and $GE=AC$, meaning that by the side-side-side property, $\triangle EFG$ is congruent to $\triangle ABC$.

The angles of congruent triangles are equal. Therefore, since $\triangle EFG$ is a right triangle, $\triangle ABC$ is also a right triangle.

The use of the SSS property here arose from a hint I found on the Internet. I would like to be able to prove that property, but have had no luck so far.1 It isn’t obvious to me why it should be true that having all sides equal guarantees congruence for triangles when it does not for other polygons.

An abbreviated proof of Theorem 2

Proposition: Two lines with slopes $m$ and $n$ are perpendicular if and only if $mn=-1$; that is, their slopes are negative reciprocals:$$n=-\frac{1}{m}$$

Let $y=mx+b$ and $y=nx+c$ be two lines such that $m\neq n$.

By Theorem 1 (from yesterday), since $m\neq n$, the two lines are not parallel. Thus, they intersect.

Let $E$ be the point at which the lines intersect.

We know from the proof of Theorem 1 that the coordinates of $E$ are $\left(\frac{c-b}{m-n},\frac{mc-nb}{m-n}\right)$.

Let $F\neq E$ be point on $y=mx+b$ with coordinates $(x_F, y_F)$ and let $G\neq E$ be point on $y=nx+c$ with coordinates $(x_G, y_G)$.

Furthermore, let $x_F=x_G=\frac{c-b}{m-n}-1$.

Perpendicular Lines

By plugging $\frac{c-b}{m-n}-1$ into both equations, we can find the values of $y_F$ and $y_G$ in terms of $m$, $n$, $b$, and $c$.

Using the formula below, we can then find the distance between each pair of points:

$$P_1P_2=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$ where $P_1=(x_1,y_1)$ and $P_2=(x_2,y_2)$.

The algebra yields the following: $FG=|m-n|$, $EF=\sqrt{1+m^2}$, and $EG=\sqrt{1+n^2}$.

Now, assume that the lines $y=mx+b$ and $y=nx+c$ are perpendicular. This means that they meet at a right angle. Thus $\triangle EFG$ is a right triangle, and by the Pythagorean Theorem

$$\left(\sqrt{1+m^2}\right)^2+\left(\sqrt{1+n^2}\right)^2=\left(|m-n|\right)^2$$$$m^2+n^2+2=m^2-2mn+n^2$$$$2=-2mn$$$$mn=-1$$

Therefore, if the two lines, $y=mx+b$ and $y=nx+c$, are perpendicular, then $mn=-1$.

Instead, assume that $mn=-1$. In that case, $$\left(\sqrt{1+m^2}\right)^2+\left(\sqrt{1+n^2}\right)^2=m^2+n^2-2mn=(m-n)^2\text{.}$$

It follows, by the converse of the Pythagorean Theorem, that $\triangle EFG$ is a right triangle. Since the right angle of a right triangle is opposite the hypotenuse, $\angle FEG$ is a right angle. Hence the lines $y=mx+b$ and $y=nx+c$ are perpendicular.

Therefore, if the slopes of two lines, $y=mx+b$ and $y=nx+c$, have a product of $-1$, then the lines are perpendicular.

I had some other ideas today, as well, including regarding the question about squares from my post Squares Again. Expect those in the next few days.

  1. To do. ↩︎

Parallel Lines

Olly / / Math Posts

Today I worked on some exercises in Analysis with an Introduction to Proof, then read the review of analytic geometry I had queued. Near the end of the review, the author quotes the following theorems, indicating that proofs can be found in his precalculus textbook:

1. Two nonvertical lines are parallel if and only if they have the same slope.
2. Two lines with slopes $m_1$ and $m_2$ are perpendicular if and only if $m_1m_2=-1$; that is, their slopes are negative reciprocals:$$m_2=-\frac{1}{m_1}$$

That got me to thinking about how I would prove those things, and I ended up spending the rest of my study time working on them. I have a complete proof of Theorem 1. It is not that exciting, but it did give me the chance to use some of the logic that I am reviewing in Analysis with an Introduction to Proof.

Proving Theorem 2 seems like the more interesting problem. What does it mean for lines to be perpendicular? If it means that they meet at a right angle, what is that? How do you prove an angle is a right angle? My best idea so far is an argument involving right triangles, but in order for it to work, I need to establish to my satisfaction not just that the Pythagorean theorem holds for all right triangles, but also that only right triangles have sides that relate in the way described in the Pythagorean theorem. It’s pretty easy to convince oneself of the latter, given the former, and I may decide that’s enough. We’ll see.

Anyway, here’s what I did for Theorem 1:

Proposition: Two nonvertical lines are parallel if and only if they have the same slope.

For two lines to be parallel means that either they do not intersect or they are the same line.

Thus, we need to prove two statements:

  1. If two nonvertical lines do not intersect or they are the same line, then they have the same slope.
  2. If two nonvertical lines have the same slope, then either they do not intersect or they are the same line.

To prove statement 2, assume that two nonvertical lines have the same slope, $m$. Their equations can be written as $y=mx+b$ and $y=mx+c$, where $b$ and $c$ are real numbers.

Now assume that the lines intersect, and let $(x_1, y_1)$ be a point that lies on both lines. It follows that $y_1=mx_1+b$ and $y_1=mx_1+c$, and thence that

$$mx_1+b=mx_1+c$$$$b=c$$

When $b=c$, the two lines have the same equation, and are thus the same line.

Thus, when two nonvertical lines have the same slope it follows that if the two lines intersect, then they are the same line.

Hence, if two nonvertical lines have the same slope, then either they do not intersect or they are the same line, which is statement 2.

(The logic in play here is: $[p\implies (q\implies r)]\equiv[p\implies(\lnot q\lor r)]$)

To prove statement 1 by contraposition, assume that two nonvertical lines have different slopes, $m$ and $n$. Their equations can be written as $y=mx+b$ and $y=nx+c$ where $m\neq n$ and $b$ and $c$ are real numbers.

Since their equations are different, they are not the same line.

Furthermore, consider the point $$\left(\frac{c-b}{m-n},\frac{mc-nb}{m-n}\right)$$ which must exist, since $m\neq n$.

Notice that $$m\left(\frac{c-b}{m-n}\right)+b=\frac{(mc-mb)+(mb-nb)}{m-n}=\frac{mc-nb}{m-n}$$ and $$n\left(\frac{c-b}{m-n}\right)+c=\frac{(nc-nb)+(mc-nc)}{m-n}=\frac{mc-nb}{m-n}\text{.}$$

Thus, the point lies on both lines and the lines intersect.

Therefore, if two nonvertical lines have different slopes, then the two lines intersect and they are not the same line.

By contraposition, it follows that if two nonvertical lines do not intersect or they are the same line, then they have the same slope, which is statement 1.

(The logic in play here is: $[\lnot p\implies (q\land\lnot r)]\equiv[\lnot(q\land\lnot r)\implies p]\equiv[(\lnot q\lor r)\implies p]$)

Stay tuned for related proofs about perpendicular lines, probably tomorrow.

Squares as Sums of Odd Numbers, Part 2

Olly / / Math Posts

Here is the promised geometric visualization of the fact that the $n$th square number is the sum of the first $n$ odd numbers. I hope it may be a bit more enjoyable for readers, who I know are mostly Olly well-wishers rather than math enthusiasts.

I actually developed this visualization between the first and second proofs I shared yesterday. As I knew the proof by induction would probably practically write itself, I got it out of the way first. I then moved on to look at the problem geometrically, hoping to gain insight that I could use to write a more illuminating proof. This geometric approach turned out to be more closely related to the proof by induction than to the second proof I came up with later, though.

Claim: The $n$th square number is the sum of the first $n$ odd numbers.

First of all, how would we represent a square number visually? One way is as a collection of dots arranged in a square, as shown below.

Visualizing Squares

Second, how can we represent an odd number visually? Well, every odd number is one more than an even number, and any even number, being divisible by 2, can be represented as two rows of the same number of dots. Thus, an odd number can be represented as two rows of the same number of dots, plus one more. (Except for 1, which is simply 1 dot.)

Visualizing Odds

Now imagine rearranging each odd number into an L shape as shown below. These L-shaped figures also have two rows of the same number of dots, plus one more.

Rearranging Odds

Next, notice how the series of L-shaped figures representing the odd numbers nest together to form a square.

Nesting Odds

Thus, the claim holds at least up to $n=5$. To draw a square representing the next square number, you would add a row and a column to this square, which you can see would be the same as adding another L-shaped figure representing the next largest odd number. So the claim must hold for each higher $n$ as well.

I also played around with a similar visualization using even numbers. The L-shaped figures representing odd numbers can be adapted to instead represent even numbers by removing the dot in the corner. When you do that, the nested figures look like this:

Nesting Evens

The center diagonal is missing from each square. Since it contains a number of dots equal to the side length of the square, the number of dots left in the $n$th square is $n^2-n$.

Accounting for the fact that the first even number, 2, corresponds to the second square, this leads to the formula

$$\sum_{i=1}^n2i=(n+1)^2-(n+1)=(n+1)[(n+1)-1]=(n+1)(n)\text{.}$$

This is what you would expect given the well known formula for the sum of the first $n$ natural numbers and can also be proven by induction. I also checked the sum of this formula and the one from yesterday. The sum of the first $n$ odd natural numbers plus the sum of the first $n$ even natural numbers should equal the sum of the first $2n$ natural numbers, which it does.

$$n^2+(n+1)(n)=n[n+(n+1)]=n(2n+1)=\frac{2n(2n+1)}{2}$$

Squares as Sums of Odd Numbers, Part 1

Olly / / Math Posts

Today was a fruitful day for math. I watched more of the Essence of Calculus series, did a couple of pages of algebra review exercises, then started on the book The Joy of X by Steven Strogatz, which I bought earlier in the week. Near the beginning of that book, the author mentions that the $n$th square number is the sum of the first $n$ odd numbers. I stopped reading at that point and went to see if I could prove the claim. I was able to come up with two proofs, as well as a way of visualizing the problem geometrically that led me to a formula for the sum of the first $n$ even numbers. I also checked that the sum of the two formulas yielded the well known one for the sum of the first $n$ natural numbers, which it did.

Proposition:
$$\sum_{i=1}^{n}(2i-1)=n^2\text{ for all }n\in\mathbb{N}\text{.}$$

The proof by induction is easy…

Proof 1 (by induction):

When $n=1$, $\sum_{i=1}^{n}(2i-1)=\sum_{i=1}^{1}(2i-1)=2(1)-1=1=1^2$.

Assume that $\sum_{i=1}^{n-1}(2i-1)=(n-1)^2$.

It follows that $\sum_{i=1}^{n}(2i-1)=\sum_{i=1}^{n-1}(2i-1)+(2n-1)=(n-1)^2+2n-1=$ $(n^2-2n+1)+2n-1=n^2$.

Therefore, by induction, the proposition holds for all $n\in\mathbb{N}$.

Proof 2:

For any $n\in\mathbb{N}$, $\sum_{i=1}^{n}(2i-1)=[2n-1]+[2(n-1)-1]+[2(n-2)-1]+…+[2(1)-1]$.

Since there are $n$ terms in the sum, there are $n$ instances of $-1$.

Thus, $\sum_{i=1}^{n}(2i-1)=2[n+(n-1)+(n-2)+…+1]-n$.

Using the well known formula for the sum of the first $n$ natural numbers, it follows that $\sum_{i=1}^{n}(2i-1)=2[\frac{n(n+1)}{2}]-n=n(n+1)-n=n[(n+1)-1]=n^2$.

Thus, the proposition holds for all $n\in\mathbb{N}$.

Stay tuned tomorrow for a geometric visualization of the problem and the formula for the sum of the first $n$ even numbers.