All posts tagged induction

My Favorite One-Liners: Part 98

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them.

I’ll use today’s quip just after introducing the methodology of mathematical induction to my students:

Induction is so easy that even the army uses it.

My Favorite One-Liners: Part 43

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them. q Q

Years ago, my first class of students decided to call me “Dr. Q” instead of “Dr. Quintanilla,” and the name has stuck ever since. And I’ll occasionally use this to my advantage when choosing names of variables. For example, here’s a typical proof by induction involving divisibility.

Theorem: If $n \ge 1$ is a positive integer, then $5^n - 1$ is a multiple of 4.

Proof. By induction on $n$ .

$n = 1$ : $5^1 - 1 = 4$ , which is clearly a multiple of 4.

$n$ : Assume that $5^n - 1$ is a multiple of 4.

At this point in the calculation, I ask how I can write this statement as an equation. Eventually, somebody will volunteer that if $5^n-1$ is a multiple of 4, then $5^n-1$ is equal to 4 times something. At which point, I’ll volunteer:

Yes, so let’s name that something with a variable. Naturally, we should choose something important, something regal, something majestic… so let’s choose the letter $q$ . (Groans and laughter.) It’s good to be the king.

So the proof continues:

$n$ : Assume that $5^n - 1 = 4q$ , where $q$ is an integer.

$n+1$ . We wish to show that $5^{n+1} - 1$ is also a multiple of 4.

At this point, I’ll ask my class how we should write this. Naturally, I give them no choice in the matter:

We wish to show that $5^{n+1} - 1 = 4Q$ , where $Q$ is some (possibly different) integer.

Then we continue the proof:

$5^{n+1} - 1 = 5^n 5^1 - 1$

$= 5 \times 5^n - 1$

$= 5 \times (4q + 1) - 1$ by the induction hypothesis

$= 20q + 5 - 1$

$= 20q + 4$

$= 4(5q + 1)$ .

So if we let $Q = 5q +1$ , then $5^{n+1} - 1 = 4Q$ , where $Q$ is an integer because $q$ is also an integer.

QED

On the flip side of braggadocio, the formula for the binomial distribution is

$P(X = k) = \displaystyle {n \choose k} p^k q^{n-k}$ ,

where $X$ is the number of successes in $n$ independent and identically distributed trials, where $p$ represents the probability of success on any one trial, and (to my shame) $q$ is the probability of failure.

1 Comment

by John Quintanilla on March 15, 2017 • Permalink

Posted in Precalculus, Probability, Tales from the Classroom, Theorems

Tagged binomial distribution, induction

Posted by John Quintanilla on March 15, 2017

https://meangreenmath.com/2017/03/15/my-favorite-one-liners-part-43/

My Favorite One-Liners: Part 28

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them. Today’s quip is one that I’ll use when simple techniques get used in a complicated way.

Consider the solution of the linear recurrence relation

$Q_n = Q_{n-1} + 2 Q_{n-2}$ ,

where $F_0 = 1$ and $F_1 = 1$ . With no modesty, I call this one the Quintanilla sequence when I teach my students — the forgotten little brother of the Fibonacci sequence.

To find the solution of this linear recurrence relation, the standard technique — which is a pretty long procedure — is to first solve the characteristic equation, from $Q_n - Q_{n-1} - 2 Q_{n-2} = 0$ , we obtain the characteristic equation

$r^2 - r - 2 = 0$

This can be solved by any standard technique at a student’s disposal. If necessary, the quadratic equation can be used. However, for this one, the left-hand side simply factors:

$(r-2)(r+1) = 0$

$r=2 \qquad \hbox{or} \qquad r = -1$

(Indeed, I “developed” the Quintanilla equation on purpose, for pedagogical reasons, because its characteristic equation has two fairly simple roots — unlike the characteristic equation for the Fibonacci sequence.)

From these two roots, we can write down the general solution for the linear recurrence relation:

$Q_n = \alpha_1 \times 2^n + \alpha_2 \times (-1)^n$ ,

where $\alpha_1$ and $\alpha_2$ are constants to be determined. To find these constants, we plug in $n =0$ :

$Q_0 = \alpha_1 \times 2^0 + \alpha_2 \times (-1)^0$ .

To find these constants, we plug in $n =0$ :

$Q_0 = \alpha_1 \times 2^0 + \alpha_2 \times (-1)^0$ .

We then plug in $n =1$ :

$Q_1 = \alpha_1 \times 2^1 + \alpha_2 \times (-1)^1$ .

Using the initial conditions gives

$1 = \alpha_1 + \alpha_2$

$1 = 2 \alpha_1 - \alpha_2$

This is a system of two equations in two unknowns, which can then be solved using any standard technique at the student’s disposal. Students should quickly find that $\alpha_1 = 2/3$ and $\alpha_2 = 1/3$ , so that

$Q_n = \displaystyle \frac{2}{3} \times 2^n + \frac{1}{3} \times (-1)^n = \frac{2^{n+1} + (-1)^n}{3}$ ,

which is the final answer.

Although this is a long procedure, the key steps are actually first taught in Algebra I: solving a quadratic equation and solving a system of two linear equations in two unknowns. So here’s my one-liner to describe this procedure:

This is just an algebra problem on steroids.

Yes, it’s only high school algebra, but used in a creative way that isn’t ordinarily taught when students first learn algebra.

I’ll use this “on steroids” line in any class when a simple technique is used in an unusual — and usually laborious — way to solve a new problem at the post-secondary level.

1 Comment

by John Quintanilla on February 28, 2017 • Permalink

Posted in Discrete mathematics, Precalculus, Tales from the Classroom

Tagged Fibonacci sequence, induction, quadratic formula, recursion, sequence, system of equations

Posted by John Quintanilla on February 28, 2017

https://meangreenmath.com/2017/02/28/my-favorite-one-liners-part-28/

My Favorite One Liners: Part 2

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them.

When doing a large computation, I’ll often leave plenty of blank space on the board to fill it later. For example, when proving by mathematical induction that

$1 + 3 + 5 + \dots + (2n-1) = n^2$ ,

the inductive step looks something like

$1 + 3 + 5 \dots + (2k-1) + (2[k+1]-1) =$

$~$

$= (k+1)^2$

So I explained that, to complete the proof by induction, all we had to do was convert the top line into the bottom line.

As my class swallowed hard as they thought about how to perform this task, I told them, “Yes, this looks really intimidating. Indeed, to quote the great philosopher, ‘You might think that I’m insane. But I’ve got a blank space, baby… so let’s write what remains.’ “

And, just in case you’ve been buried under a rock, here’s the source material for the one-liner (which, at the time of this writing, is the fifth-most watched video on YouTube):

What I Learned from Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Part 9

When teaching students mathematical induction, the following series (well, at least the first two or three) are used as typical examples:

$1 + 2 + 3 + \dots + n = \displaystyle \frac{n(n+1)}{2}$

$1^2 + 2^2 + 3^2 + \dots + n^2 = \displaystyle \frac{n(n+1)(2n+1)}{6}$

$1^3 + 2^3 + 3^3 + \dots + n^3 = \displaystyle \frac{n^2(n+1)^2}{4}$

$1^4 + 2^4 + 3^4 + \dots + n^4 = \displaystyle \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}$

What I didn’t know (Gamma, page 81) is that Johann Faulhaber published the following cute result in 1631 (see also Wikipedia): If $k$ is odd, then

$1^k + 2^k + 3^k + \dots + n^k = f_k(n(n+1))$ ,

where $f_k$ is a polynomial. For example, to match the above examples, $f_1(x) = x/2$ and $f_3(x) = x^2/4$ . Furthermore, if $k$ is even, then

$1^k + 2^k + 3^k + \dots + n^k = (2n+1) f_k(n(n+1))$ ,

where again $f_k$ is a polynomial. For example, to match the above examples, $f_2(x) = x/6$ and $f_3(x) = x(3x-1)/30$ .

When I researching for my series of posts on conditional convergence, especially examples related to the constant $\gamma$ , the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites — while giving the book a very high recommendation.

4 Comments

by John Quintanilla on October 9, 2016 • Permalink

Posted in Discrete mathematics, History, Precalculus

Tagged induction, series

Posted by John Quintanilla on October 9, 2016

https://meangreenmath.com/2016/10/09/what-i-learned-from-reading-gamma-exploring-eulers-constant-by-julian-havil-part-9/

Mathematical induction and blank space

I tried out a one-liner in class that I’d been itching to try all summer.

I was introducing my students to proofs by mathematical induction; my example was showing that

$1 + 3 + 5 + \dots + (2n-1) = n^2$ .

After describing the principle of mathematical induction, I wrote out the $n = 1$ step and the assumption for $n = k$ :

$n=1$ : $1=1^2$ , so this checks.

$n =k$ : Assume that $1 + 3 + 5 + \dots + (2k-1) = k^2$ .

Then, for the inductive step, I had my students tell me what the left- and right-hand side would be if I substituted $k+1$ in place of $n$ . I wrote the answer for the left-hand side at the top of the board, the answer for the right-hand side at the bottom of the board, and left plenty of blank space in between the two (which I would fill in shortly):

$n = k+1$ :

$1 + 3 + 5 \dots + (2k-1) + (2[k+1]-1) =$

$~$

$= (k+1)^2$

So I explained that, to complete the proof by induction, all we had to do was convert the top line into the bottom line.

The one-liner provoked the desired response from my students… and after the laughter died down, we then worked through the end of the proof.

And, just in case you’ve been buried under a rock for the past few months, here’s the source material for the one-liner (which, at the time of this writing, is the second-most watched video on YouTube):

1 Comment

by John Quintanilla on September 5, 2015 • Permalink

Posted in Discrete mathematics, Humor, Precalculus, Tales from the Classroom

Tagged induction

Posted by John Quintanilla on September 5, 2015

https://meangreenmath.com/2015/09/05/mathematical-induction-and-blank-space-2/

Proving theorems and special cases (Part 5): Mathematical induction

Today’s post is a little bit off the main topic of this series of posts… but I wanted to give some pedagogical thoughts on yesterday’s post concerning the following proof by induction.

Theorem: If $n \ge 1$ is a positive integer, then $5^n - 1$ is a multiple of 4.

Proof. By induction on $n$ .

$n = 1$ : $5^1 - 1 = 4$ , which is clearly a multiple of 4.

$n$ : Assume that $5^n - 1$ is a multiple of 4, so that $5^n - 1 = 4q$ , where $q$ is an integer. We can also write this as $5^n = 4q + 1$ .

$n+1$ . We wish to show that $5^{n+1} - 1$ is equal to $4Q$ for some (different) integer $Q$ . To do this, notice that

$5^{n+1} - 1 = 5^1 5^n - 1$

$= 5 \times 5^n - 1$

$= 5 \times (4q + 1) - 1$ by the induction hypothesis

$= 20q + 5 - 1$

$= 20q + 4$

$= 4(5q + 1)$ .

So if we let $Q = 5q +1$ , then $5^{n+1} - 1 = 4Q$ , where $Q$ is an integer because $q$ is also an integer.

My primary observation is that even very strong math students tend to have a weak spot when it comes to simplifying exponential expressions (as opposed to polynomial expressions). For example, I find that even very good math students can struggle through the logic of this sequence of equalities:

$2^n + 2^n = 2 \times 2^n = 2^1 \times 2^n = 2^{n+1}$ .

The first step is using the main stumbling block. Students who are completely comfortable with simplifying $x + x$ as $2x$ can be perplexed by simplifying $2^n + 2^n$ as $2 \times 2^n$ . I attribute this to lack of practice with this kind of simplification in lower grade levels.

Here’s another algoebraic stumbling block that I’ve often seen: at the beginning of the $n+1$ case, some students will make the following mistake:

$5^{n+1} - 1 = 5^1 5^n - 1 = 5 (4q) = 4 (5q) = 4Q$ .

Because these students end with a multiple of 4, they fail to notice that the second equality is incorrect since

$5^1 5^n - 1 \ne 5^1 (5^n - 1)$ .

Again, I attribute this to lack of practice with simplifying exponential expressions in lower grade levels… as well as being a little bit over-excited upon seeing $5^n - 1$ and wishing to use the induction hypothesis as soon as possible.

1 Comment

by John Quintanilla on June 20, 2015 • Permalink

Posted in Algebra II, Precalculus, Theorems

Tagged divisibility, exponent, induction

Posted by John Quintanilla on June 20, 2015

https://meangreenmath.com/2015/06/20/proving-theorems-and-special-cases-part-5/

Proving theorems and special cases (Part 4): Mathematical induction

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct. In the previous two posts, we saw that a statement that’s true for the first 40 cases or even the first $10^{316}$ cases may not be true for all cases.

This is the reason that mathematical induction is important, as it provides a way to build from previous cases to prove that the next case is still correct, thus proving that all cases are correct.

Theorem: If $n \ge 1$ is a positive integer, then $5^n - 1$ is a multiple of 4.

Proof. By induction on $n$ .

$n = 1$ : $5^1 - 1 = 4$ , which is clearly a multiple of 4.

$n$ : Assume that $5^n - 1$ is a multiple of 4, so that $5^n - 1 = 4q$ , where $q$ is an integer. We can also write this as $5^n = 4q + 1$ .

$n+1$ . We wish to show that $5^{n+1} - 1$ is equal to $4Q$ for some (different) integer $Q$ . To do this, notice that

$5^{n+1} - 1 = 5^n 5^1 - 1$

$= 5 \times 5^n - 1$

$= 5 \times (4q + 1) - 1$ by the induction hypothesis

$= 20q + 5 - 1$

$= 20q + 4$

$= 4(5q + 1)$ .

So if we let $Q = 5q +1$ , then $5^{n+1} - 1 = 4Q$ , where $Q$ is an integer because $q$ is also an integer.

QED

In the above proof, we were able to build from the $n$ case to reach the $n +1$ case. In this sense, to answer the student’s question, it is possible to prove a theorem by first proving a special case of the theorem.

By contrast, when trying to “prove” that $n^2 - n + 41$ is prime for all integers $n$ , the proposition is true for $1 \le n \le 40$ , but it’s just a coincidence… there was no string of logic that connected these first 40 cases other than the coincidence that they all were correct.

1 Comment

by John Quintanilla on June 19, 2015 • Permalink

Posted in Precalculus, Theorems

Tagged induction, primes

Posted by John Quintanilla on June 19, 2015

https://meangreenmath.com/2015/06/19/proving-theorems-and-special-cases-part-4/

Proving theorems and special cases (Part 3): Skewes’ number

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct.

In the first two posts of this series, we showed conjectures could be true for the first 40 cases or even the first 900 million odd cases but fail on the next case. In today’s post, I’ll describe a conjecture that, for hundreds of years, was thought to be true for all integers $n$ and has since been shown to be true for all $n \le 10^{316}$ . However, despite being true for so many special cases, the conjecture is false.

Let’s absorb the above paragraph again. The conjecture “ $n^2 - n + 41$ is always prime” was true for the first 40 cases before failing. By contrast, the conjecture I’m about the describe is true for the first (approximately) 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000 cases before failing.

The conjecture in question concerns the number of prime numbers $\pi(n)$ that are less than or equal to $n$ . For example:

There are four prime numbers less than 10 (namely 2, 3, 5, 7), and so $\pi(10) = 4$ .

There are eight prime numbers less than 10 (namely 2, 3, 5, 7, 11, 13, 17, 19), and so $\pi(20) = 8$ .

One of the classic problems in mathematics, often called the Prime Number Theorem, is estimating the value of $\pi(n)$ when $n$ is large. It turns out that one way of approximating $\pi(n)$ is through the logarithmic integral

$\hbox{Li}(n) = \displaystyle \int_2^n \frac{dx}{\ln x}$

Indeed, the Prime Number Theorem states that

$\pi(n) \sim \hbox{Li}(n)$ ,

$\displaystyle \lim_{n \to \infty} \frac{\pi(n)}{\hbox{Li}(n)} = 1$ .

This asymptotic relationship was proven by the eminent mathematician Karl Friedrich Gauss.

With that as prelude, here’s the false conjecture. For decades, luminaries of mathematics, including Gauss and Bernhard Riemann, conjectured that

$\pi(n) < \hbox{Li}(n)$ for all integers $n$

based on the available numerical evidence at the time. However, this conjecture was proven false in the 20th century by the British mathematician John Littlewood. No only did Littlewood show that there is a value of $n$ so that $\pi(n) > \hbox{Li}(n)$ , but he also showed that the graphs of $\pi(n)$ and $\hbox{Li}(n)$ cross over each other infinitely many times!

Littlewood proved his theorem over 100 years ago in 1914. Today, even with modern computing power, we still do not precisely know the first value of $n$ for which $\pi(n) > \hbox{Li}(n)$ . This number is called Skewes’ number, in honor of the mathematician who first found (in 1955) an upper bound on this first crossing point. The bound that he found was absolutely enormous: he showed that $\pi(n) > \hbox{Li}(n)$ for some $n$ less than

$\displaystyle 10^{\displaystyle 10^{10^{34}}}$

More recent work has established that the first crossover likely occurs in the vicinity of $n \approx 1.397 \times 10^{316}$ .

Whoever first evaluates Skewes’ number exactly will surely have a nice feather in his/her cap for completing a task that mystified both Gauss and Riemann.

References:

http://mathworld.wolfram.com/PrimeNumberTheorem.html

http://mathworld.wolfram.com/SkewesNumber.html

http://mathworld.wolfram.com/PrimeCountingFunction.html

http://mathworld.wolfram.com/LogarithmicIntegral.html

1 Comment

by John Quintanilla on June 18, 2015 • Permalink

Posted in Precalculus, Theorems

Tagged induction, primes

Posted by John Quintanilla on June 18, 2015

https://meangreenmath.com/2015/06/18/proving-theorems-and-special-cases-part-3/

Proving theorems and special cases (Part 2): The Pólya conjecture

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct.

In yesterday’s post, we showed that the conjecture “ $n^2 - n + 41$ is a prime number for all positive integers $n$ ” is true for $1 \le n \le 40$ but fails for $n = 41$ . In today’s post, I’ll describe a conjecture that is true for plenty more special cases before becoming false.

The Pólya conjecture (see here and here for more information) stated that 50% or more of the natural numbers less than or equal to any given number have an odd number of prime factors (counting multiplicity). For example:

$2$ has one prime factor: odd

$3$ has one prime factor: odd

$4 = 2 \times 2$ has two prime factors: even

$5$ has one prime factor: odd

$6 = 2 \times 3$ has two prime factors: even

$7$ has one prime factor: odd

$8 = 2 \times 2 \times 2$ has three prime factors: odd

$9 = 3 \times 3$ has two prime factors: even

$10 = 2 \times 5$ has two prime factors: even

So of the numbers less than or equal to 10, five have an odd number of prime factors, and only four have an even number of prime factors.

The Pólya conjecture was first proven false by producing a counterexample in the vicinity of $1.845 \times 10^{361}$ . It turns out that the smallest counterexample is 906,150,257. In other words, the Pólya conjecture is true for the first 906,150,256 cases but fails on the next case.

1 Comment

by John Quintanilla on June 17, 2015 • Permalink

Posted in Precalculus, Theorems

Tagged induction, primes

Posted by John Quintanilla on June 17, 2015

https://meangreenmath.com/2015/06/17/proving-theorems-and-special-cases-part-2/

Search for:
Follow Blog via Email

Enter your email address to follow this blog and receive notifications of new posts by email.
Top Posts & Pages
Archives
Categories
- Algebra I (170)
- Algebra II (266)
- Bases (43)
- Calculus (224)
- Chemistry (9)
- Computer science (9)
- Discrete mathematics (216)
- Elementary (146)
- Engagement (664)
- Geometry (205)
- Guest presenter (389)
- History (51)
- Humor (230)
- News Clips (113)
- Physics (35)
- Popular Culture (213)
- Pre-Algebra (153)
- Precalculus (476)
- Preparing for college (12)
- Probability (82)
- Statistics (77)
- Tales from the Classroom (210)
- Technology (75)
- Theorems (152)
- Uncategorized (53)
Tags
angle arccosine arcsine arctangent area bag of tricks binary circle combinatorics Common Core complex numbers compound interest conceptual barrier confidence interval convex polygons cosine decimal De Moivre's Theorem derivative differential equation distributive law divisibility division algorithm e exponent exponential factorial factoring fraction function gamma geometric series graph high-stakes testing hypothesis test index to a series of posts induction integral inverse function law of cosines law of sines limit logarithm logic MAA magic trick multiplication Pascal's triangle perpendicular polar coordinates polynomial primes PRIMUS proof Pythagorean theorem Pythagorean trig identities quadratic formula regression residue sequence series sine slope sphere sports square root system of equations tangent Taylor series textbook problems triangle trigonometry unsolved problems volume xkcd
Meta

All posts tagged induction

Follow Blog via Email

Top Posts & Pages

Archives

Categories

Tags

Meta