LNK2LRN™ 2009/10 AP Physics B May 13-25: Advanced Topics.

Mathematical Induction

The need for proof

Most people today are lazy. We watch way too much television and are content to

accept things as true without question. If we see something that works a few times

in a row, we're convinced that it works forever.

Regions of a Circle

Consider a circle with n points on it. How many regions will the circle be divided

into if each pair of points is connected with a chord?

2 points 2 regions = 21	3 points 4 regions = 22	4 points 8 regions = 23	5 points 16 regions = 24

At this point, probably everyone would be convinced that with 6 points there would

be 32 regions, but it's not proved, it's just conjectured. The conjecture is that the

number of regions when n points are connected is 2^{n -1}.

Will finding the number of regions when there are six points on the circle prove the

conjecture? No. If there are indeed 32 regions, all you have done is shown another

example to support your conjecture. If there aren't 32 regions, then you have proved

the conjecture wrong. In fact, if you go ahead and try the circle with six points on it,

you'll find out that there aren't 32 regions.

You can never prove a conjecture is true by example.

But you can prove a conjecture is false by finding a counter-example.

To prove a conjecture is true, you need some more formal methods of proof. One

of these methodsis the principle of mathematical induction.

Principle of Mathematical Induction (Plain English)

1. Show something works the first time.
2. Assume that it works for this time,
3. Show it will work for the next time.
4. Conclusion, it works all the time

Principle of Mathematical Induction (Mathematics)

1. Show true for n = 1
2. Assume true for n = k
3. Show true for n = k + 1
4. Conclusion: Statement is true for all n >= 1

The key word in step 2 is assume. You are not trying to prove it's true for n = k, you're

going to accept on faith that it is, and show it's true for the next number, n = k + 1. If it

later turns out that you get a contradiction, then the assumption was wrong.

Annotated Example of Mathematical Induction

Prove 1 + 4 + 9 + ... + n² = n (n + 1) (2n + 1) / 6 for all positive integers n.

Identify the general term and n^th partial sum before beginning the problem

The general term, a_n, is the last term on the left hand side. a_n = n²
The n^th partial sum, S_n, is the right hand side. S_n = n (n + 1) (2n + 1) / 6

Find the next term in the general sequence and the series

The next term in the sequence is a_k+1 and is found by replacing n with k+1 in the

general term of the sequence, a_n.

a_k+1 = ( k + 1 )²

The next term in the series is S_k+1 and is found by replacing n with k+1 in the n^th

partial sum, S_n. You may wish to simplify the next partial sum, S_k+1
S_k+1 = (k+1) [ (k+1) + 1 ] [ 2(k+1) + 1 ] / 6
S_k+1 = ( k + 1 ) ( k + 2 ) ( 2k +3 ) / 6 (This will be our Goal in step 3)

We will use these definitions later in the mathematical induction process.

We're now ready to begin.

1. Show the statement is true for n = 1, that is, Show that a₁ = S₁.

a₁ is the first term on the left or you can find it by substituting n=1 into the formula for

 the general term, a_n. S₁ is found by substituting n=1 into the formula for the n^th

partial sum, S_n.

LHS: a₁ = 1
RHS: S₁ = 1 ( 1+1 ) [ 2(1) + 1 ] / 6 = 1(2)(3) / 6 = 1

So, you can see that the left hand side equals the right hand side for the first term, so

we have established the first condition of mathematical induction.

2. Assume the statement is true for n = k

The left hand side is the sum of the first k terms, so we can write that as S_k. The right

hand side is found by substituting n=k into the S_n formula.

Assume that S_k = k ( k + 1 ) ( 2k + 1 ) / 6

3. Show the statement is true for n = k+1

What we are trying to show is that S_k+1 = ( k + 1 ) ( k + 2 ) ( 2k +3 ) / 6. This was our

goal from earlier.

We begin with something that we know (assume) is true and add the next term, a_k+1,

to both sides.

S_k + a_k+1 = k ( k + 1 ) ( 2k + 1 ) / 6 + a_k+1

On the left hand side, S_k + a_k+1 means the "sum of the first k terms" plus "the k+1 term",

which gives us the sum of the first k+1 terms, S_k+1. This often gives students difficulties,

so lets think about it this way. Assume k=10. Then S_k would be S₁₀, the sum of the first

10 terms and a_k+1 would be a₁₁, the 11^th term in the sequence. S₁₀ + a₁₁ would be the

sum of the 10 terms plus the 11^th term which would be the sum of the first 11 terms.

On the right hand side, replace a_k+1 by ( k+1)², which is what you found it was before

beginning the problem.

S_k+1 = k ( k + 1 ) ( 2k + 1 ) / 6 + ( k + 1 )²

Now, try to turn your right hand side into goal of ( k + 1 ) ( k + 2 ) ( 2k +3 ) / 6.
You need to get a common denominator, so multiply the last term by 6/6.

S_k+1 = k ( k + 1 ) ( 2k + 1 ) / 6 + 6 ( k + 1 )² / 6

Now simplify. It is almost always easier to factor rather than expand when simplifying.

This is especially aided by the fact that your goal is in factored form. You can use that to

help you factor. You know that you want a (k+1) (k+2) (2k+3) in the final form. We see

right now that there is a (k+1) that is common to both of those, so let's begin by

factoring it out.

S_k+1 = ( k + 1) [ k ( 2k + 1 ) + 6 ( k + 1 ) ] / 6

What's left inside the brackets [ ] doesn't factor, so we expand and combine like terms.

S_k+1 = ( k + 1) ( 2k² + k + 6k + 6 ) / 6
S_k+1 = ( k + 1) ( 2k² + 7k + 6 ) / 6

Now, try to factor 2k² + 7k + 6, keeping in mind that you need a (k+2) and (2k+3) in the

goal that you don't have yet.

S_k+1 = ( k + 1) ( k + 2 ) ( 2k + 3 ) / 6

That's what our goal was. That's what we were trying to show. That means we did it!

Conclusion

Now we state our conclusion by saying "Therefore, by the principle of mathematical

induction, 1 + 4 + 9 + ... + n² = n (n + 1) (2n + 1) / 6 for all positive integers n."

Sums of the Powers of the Integers

Now, we're going to look at the sum of the whole number powers of the natural numbers.

Sigma Notation = Closed Form	Expanded
	1 + 1 + 1 + ... + 1 (n times)
	1 + 2 + 3 + ... + n
	1 + 4 + 9 + ... + n2
	1 + 8 + 27 + ... + n3
	1 + 16 + 81 + ... + n4
	1 + 32 + 243 + ... + n5

The closed form for a summation is a formula that allows you to find the sum simply

by knowing the number of terms.

Some Notes on Calculus Applications

Instantaneous velocity can be computed by finding the slope of a tangent

line at any point on the graph of displacement as a function of time, or

v = Δx/Δt.

Instantaneous acceleration can be computed by finding the slope of a

tangent line at any point on the graph of velocity as a function of time, or

a = Δv/Δt.

Velocity and acceleration can also be evaluated using another method

involving limits and the first derivative. Here, v = dx/dt and a = dv/dt.

Integral calculus can be used to derive velocity from acceleration, and

displacement from velocity. In terms of Calculus, v = ∫a dt + C.

Similarly, x = ∫v dt + C.

View the Slides

Answers to Calculus Handout: 1. 6   2. 19   3. 6   4. 11   5. c   6. d  

7. b   8. 1/3, 1   9. a   10. (1, -2), (-1, 2)   11. 14 m/s   12. a   13. c  

14. b   15. 264 ft/s

THE AP PHYSICS B ARCHIVES Ch.1: Physics Intro. Ch.2: Linear Motion. Ch.3: 2-Dim Motion. Ch.4&5: Newton's Laws. Ch.6&7: Work/Momentum. Ch.8&9: Rotary Motion. Ch.10: SHM. Ch.11: Fluids. Ch.12&13: Temp.&Heat. Ch.14&15: Thermodynamics. Semester Review. Ch.16: Waves&Sound. Ch.17: Wave Superposition. Ch.18: Electric Fields. Ch.19: Electric Potential. Ch.20: Electric Circuits. Ch.21&22: Magnetism. Ch.24: Electromagnetic Waves. Ch.25-26-27: Geometric Optics. Ch.29-30-31-32: Atomic/Nuclear.