Math 3303



Math 3303

Module 1 A Chapter 1 and Chapter 2

Module 1 B Chapter 3

Homework

Grading: 20 % homework

30 % midsemester*

20 % poppers

30 % final* *at CASA Testing by appointment

Open CourseWare and click on EMCF: Popper 01

Chapter 1, page 1

The authors discuss counting.

| | | | |

|Addition |None |Few |Many |

| | | | |

|None | | | |

| | | | |

|Few | | | |

| | | | |

|Many | | | |

The problem:

Now, we use a place value system (base 10).

Our digits:

Check out

The authors then launch into a discussion of “the algebra of polynomials” with an eye toward discussion the arithmetic of natural numbers.

Let me fill in a bit of background and then move through pages 2 and 3

First: what is a polynomial?

[pic]

Where the coefficients are real numbers and the exponents are whole numbers.

Examples:

[pic] [pic] [pic]

NOT polynomials

[pic] [pic] [pic]

Now the algebra of polynomials is adding, subtracting, and multiplying polynomials to get new polynomials.

Let’s look at how numbers and polynomials work together…assume x = 10

Number Associated polynomial Place value!

3 [pic]

12 [pic]

103 [pic]

And some arithmetic with numbers and polynomials:

Multiply 307 by 43

Set up the associated polynomials and multiply

Do you see the similarities?

Now the arithmetic of polynomials works no matter what the base!

In computers we use binary (base 2) and hex (base 12). In other places, the counting system is historically base 5 (five fingers!).

Doing arithmetic in ANY base is our goal here.

[pic]

Check it out: base 10, base 2, and base 5

The polynomial approach is very Big Picture (looking out over The Forest), while actually doing the arithmetic in any given base is walking among the trees watching out for roots!

One more example and then back to the book:

[pic]

Base 10

Base 5

Looking at page 4

Translating from one base to another:

Let’s take [pic]

And then we’ll put it in polynomial form base 2:

And polynomial form base 10:

P1 Q1

Which of the following is NOT a polynomial?

A. [pic]

B. [pic]

C. [pic]

D. [pic]

E. They’re ALL polynomials!

Page 8 Roman numerals

Are positional numbers but don’t have “place value” like our Arabic numerals. They’re difficult to add and subtract – in fact you have to do that in your homework!

Use the internet wisely on that problem!

Chapter 2 page 11

Google Divisibility Rules – or look on my website under Module 1. We’re interested in the “WHY” behind the rule!

On page 12 is a cute Gauss story – just imagine having a kid that bright in your class!

On to divisibility by 3:

If the sum of the digits is divisible by 3, then the number is divisible by 3

For example: 114

Page 13: The WHY

Take an arbitrary 4 digit number: a, bcd

This is, in polynomials with [pic]x = 10: [pic]

This shows how it works with an abstract number. Let’s look at it with 114:

The book shows divisibility by 11. You have to do divisibility by 4 in your homework

This process of illustrating is NOT a proof! It just shows without proving. And proving when there’s an infinite number of steps in the process is done with a process called “induction”.

Now’s let’s look on page 14 at a fairly typical math scenario:

Someone wants to add the first n even numbers…quickly.

2

2 + 4 = 6

2 + 4 + 6 = 12

And so on…and this person notices a pattern….and before long comes up with a formula:

An even number is 2(n) where n is a counting number…so adding some of them is shown as

2 + 4 + 6 + …+ 2n

And the person claims that this string of adding is equal to [pic]

Note that “n” has to be the same on the right hand side AND the left hand side

“n”= 1

2 = [pic] yes!

“n” = 2

2 + 4 = [pic]

…and so on in this pattern…until you get to n = 5!

2 + 4 + 6 + 8 + 10 = 30 and the formula with n = 5 gives you 54.

OOPS. The person was wrong! And this is called a “counter example”

Now sometimes the counter example comes at 47 or 115…sometimes the formula is TRUE and you’ll NEVER get a counterexample!

When the formula is true, we can prove it “by induction”!

Note: much later in the book (page 147) there’s a “formula” for creating prime numbers that works up to n = 79! Then it fails. It turns out that there is NO formula for creating primes…and there’s a proof of this that we’ll look at. Just imagine working the darn formula 80 times before getting a counterexample though!

Break here for second taping!

Now, how do we prove formulas by induction? The authors show an example on pages 15, 16, and 17. I want to do it out a bit more formally.

There’s a process for it.

Write down the claim – there will be 2 sides, a left hand side (LHS) and a right hand side (RHS) separated by an “=” sign.

Step 1: show it works for the 1st n…

n = 1 unless otherwise noted

Step 2: assume it works up to some number “k” and rewrite it using k for n

n = k

Step 3: Add the NEXT natural number in line to both sides. Box off the RHS and work only with the LHS to prove that the 2 sides are equal!

Done!

Here’s a different example than the example in the book:

The claim: The sum of n cubes is [pic].

Now let’s go through the steps:

Write the claim out:

[pic]

Now, nothing is specified for n … if it were there would be something like “n > 3” written right up there with the original claim. So we’ll start Step 1 with n = 1.

And we’ll show it for n = 2, 3, and 4 just for extra (these additional showings are just for teaching purposes and not required).

Step 2…assume that it works all the way up to n = k and rewrite it:

Step 3 Carefully add the next natural number, k + 1, to both sides. Box of the RHS and work, work, work

Ok. That’s an induction proof. The basic idea is that you show that it works for a number k, and then you show that it works for the NEXT number k + 1…so it works for all numbers.

Here are the steps again:

Write the claim

Show it for the first n

Assume it for the first k numbers

Show it works for the NEXT number, k + 1

There are some examples on my website for you to look at!

Then the authors change gear!

We’ll come back to induction proofs in a bit. Right now let’s look at square numbers. In the old days (before Christ was born) square numbers were quite special and had religious significance. They also had a physical representation!

Square numbers: [pic]

The set of triangular numbers T = {[pic]} and the indices indicate how many rows and columns of points the number has…

Note that the Square numbers and the Triangular numbers are related!

The sum of adjacent triangular numbers is a square number (this would be proved with an induction proof!).

Moving on to page 19 – here’s a little factette:

The sum of the first n square numbers is [pic].

That’s a claim and we’re going to prove it by induction!

1 + 4 + 9 + 16 +…n(n) = [pic]

Step 1

Show it for n = 1 (and a couple more, just for illustration)

Step 2 Assume it for n = k

Write that out

Step 3 – prove it for n = k + 1

Popper 1, Question 2

Is there a triangular number between 10 and 15?

A. yes

B. no

Now here’s one that’s even harder! Are there any numbers that are BOTH square and triangular?

Yes! 1 is both

1,225 is both

41, 616 is both

1, 413,721 is both

There are an infinite number of boths…but they get big, really big, fast!

Break here for the third taping!

Pages 20 – 23

Now we’ll continue to look at numbers, but we’ll be looking at REALLY SPECIAL numbers…

Perfect numbers.

Now perfect numbers were known before Christ was born and they had even deeper religious significance than the square or the triangular numbers!

Here’s the definition of a perfect number:

A perfect number is equal to the sum of it’s proper divisiors plus 1.

Oh, so what’s a PROPER divisor? A proper divisor is strictly bigger than 1 and strictly smaller than the number itself.

For example:

Let’s look at 4. The divisors of 4 are 1, 2, and 4. The proper divisor is 2. Let’s see if 4 is perfect: 2 + 1 = 3, which is not 4. No, 4 is a kind of number called deficient…the sum of the proper divisors plus 1 is less than 4.

Let’s look at 12. The divisors of 12 are 1, 2, 3, 4, 6, and 12. The proper divisors are: 2, 3, 4, 6. These added plus one is 16, which is more than 12…so 12 is a kind of number called abundant, not perfect.

Let’s look at 6. The proper divisors are 2 and 3. 2 + 3 + 1 = 6. PERFECT!

It turns out that the natural numbers can be sorted into special subsets:

{1} U {deficients}U{abundants}U{perfects}. Each natural number goes into exactly ONE subset and the union of all four sets is the natural numbers.

There are a infinite number of Perfects. The first one is 6, then 28, then 496, then [pic]

And so on forever. Perfect numbers play a HUGE role in number theory and it’s important that you know what they are so we can make use of them later in the semester!

All known perfect numbers are even – just a little factette.

And people have been seeing patterns in them for just forever. Let’s look at a list of them and see if you can see the pattern:

[pic]

Here’s what people finally noticed in the 1800’s: the pattern is [pic]

BUT, interestingly, NOT every prime works. Eleven doesn’t work…the pattern skips from 7 to 13 because of this!

So we finally got to a theorem:

If [pic]is itself a prime number, then [pic]is perfect!

Let’s check out some of those second factors above:

[pic]

These special factors [pic]that are prime are called “Mersenne Primes” after the mathematician who saw how important they were. All known Mersenne Primes are odd.

Popper 1, Question 3

Which of the following does NOT describe the number 2?

A. even

B. prime

C. perfect

D. positive

E. has no proper divisors

More on Mersenne Primes:

They have their own organization and website:



There’s a huge effort to find the next one:

The Great Internet Mersenne Prime Search (GIMPS) – you can volunteer to be part of this.

On 4/12/09 Dr. Odd Mogner Strindmo from Melhus Norway found the 47th Mersenne Prime.

Popper 1, Question 4

Which of the following does NOT describe 3?

A. Mersenne Prime D. perfect

B. odd E. [pic]

C. positive

What we are doing to a certain extent here is looking at the set of Natural numbers and creating what are called “partitions” on the set. A partition is a way of allocating each set element to one and only 1 subset so that each set element is tucked into a subset and none of the subsets share elements.

The classic partition on the naturals is Evens and Odds. Each natural number is either even or odd (not BOTH and not NEITHER). You get 2 subsets that are disjoint and when you union them back up you get the Naturals back.

Another partition is: {1}U{Primes}U{Composites}

Earlier in the notes is the 4 part partition of {1}U{Abundants}U{Deficients}U{Perfects}

Partitions show up often in math and in life:

We regularly partition clothes into dirty and clean. Kids: boys and girls. Real number: {negatives}U{0}U{positives}. Triangles: {obtuse}U{acute}U{right}.

Partitions are helpful because you then work with a subset with a well-defined property…each set element gets tucked away and you can retrieve the original set easily.

We will revisit partitions OFTEN in 3303.

Popper 1, Question 5

An alternate definition for prime numbers is: A prime number is a number with NO proper divisors.

A. true

B. false.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download