[PDF] Problem Solving for Math Competitions Harm Derksen





Previous PDF Next PDF



1. 1 + 2 + 3 + ··· + n = n(n + 1)(2n + 1) 6 Proof: For n = 1 the

In Exercises 1-15 use mathematical induction to establish the formula for n ? 1. 1. 1. 2. + 2. 2. + 3. 2. + ··· + n. 2. = n(n + 1)(2n + 1).



MATHEMATICAL INDUCTION SEQUENCES and SERIES

?n is always divisible by 30. Use the fact that n. 5. ?n = (n?1)n(n+1)(n. 2. +1) to prove that it is divisible by 2 and 3 as well as 5.



Problem: For each positive integer n the formula 1 · 3+2 · 4+3 · 5 +

1 · 3+2 · 4+3 · 5 + ··· + n(n + 2) = n(n + 1)(2n + 7). 6 is valid. Proof: (formal style; it is good to do a few proofs this way) We will use the Principle 



Proof by Induction - University of Plymouth

12-Feb-2006 Example 3: for n a natural number prove that: 1) if n ? 2 then n3 ? n is always divisible by 3



X X

2! + t4. 4! 3 t6. 6! + 17 t8. 8!



Problem Solving for Math Competitions Harm Derksen

* Prove that. 12 + 22 + ··· + n2 = n(n + 1)(2n + 1). 6 for all positive integers n. Exercise 1.2. * Show that. 1 ?. 1. 2. +. 1. 3. ? 



BINOMIAL THEOREM

8.1.3 Some important observations. 1. The total number of terms in the binomial expansion of (a + b)n is n + 1 i.e. one more than the exponent n. 2.



CS240 Solutions to Induction Problems Fall 2009 1. Let P(n) be the

If we had shown P(3) as our basis step then the inequality would only be proven for n ? 3. 2. For any positive integer n n. ? i=1. 1 i(i + 1). = 1. 1 · 2.



IMO 2008 Shortlisted Problems

(a ? 1)(b ? 1)(c ? 1) = abc. ?=(a ? 1)2 ? 4a(a ? 1) = (1 ? a)(1 + 3a). ... (i) f(2n ? t(m)) ? 3(n?1)/2 if 2n + m is divisible by 3;.



Untitled

principle of induction P(n) is true for all positive integers n > 1. herefore each term in the product (1+2+22)(1 +3 +3² +3³)(1 +.



Polynomials II - Divisibility and Irreducibles

So now for instance x2 ?2 is not divisible by x? ? 2 over Q since x? ? 2 doesn’t exist over Q Problem 9 Show that x2?2 is irreducible over Q (Hint: Suppose it were reducible What would the degrees of the factors have to be and what does that mean?) Problem 10 Show that x3 ?2 is irreducible over Q (Hint: This is similar



Math 115 Exam  Solutions - Colorado State University

1+n2 = 0 and (ii) the sequence of terms 1+n2 are decreasing To see (i) notice that we can divide numerator and denominator by n2 to get lim n?? 1 n2 ·n 1 n2 (1+n 2) = lim n?? 1 n 1 n2 +1 = 0 To see (ii) let f(x) = x 1+x2 Then f0(x) = (1+x2)·1?x·2x (1+x2)2 = 1?x2 (1+x2)2 ? 0 for x ? 1 Therefore f is a decreasing



3 Mathematical Induction 31 First Principle of

3 MATHEMATICAL INDUCTION 89 Which shows 5(n+ 1) + 5 (n+ 1)2 By the principle of mathematical induction it follows that 5n+ 5 n2 for all integers n 6 Discussion In Example 3 4 1 the predicate P(n) is 5n+5 n2 and the universe of discourse

How to prove n is true for all integers n 1?

Mathematical induction can be used to prove that a statement about n is true for all integers n ? 1. We have to complete three steps. In the basis step, verify the statement for n = 1. In the inductive hypothesis, assume that the statement holds when n = k for some integer k ? 1.

Does f(n) = n 1+n2 converge?

Therefore, f is a decreasing function in the relevant range, so the terms f(n) =n 1+n2are decreasing. 1 We know that the series converges, but we need to determine whether it converges absolutely or not. In other words, we must determine if X? n=1 (?1) nn 1+n2 = X? n=1 n 1+n2 . converges or not.

Is p divisible by Q over C?

Definition 1Let p and q be polynomials in the complex numbers C. We say that p is divisble by q over C if there exists a polynomial r such that p(z) = q(z)r(z). Problem 1 By long division (which we learned how to do last week), answer the following: • Is x3?2x2+ x?2 divisible by x?2 over C?

Problem Solving

for Math Competitions

Harm Derksen

CHAPTER 1

Mathematical Induction

1. The induction principle

Suppose that we want to prove that

\P(n)is true for every positive integern", whereP(n) is a proposition (statement) which depends on a positive integern. ProvingP(1), P(2),P(3), etc., would take an innite amount of time. Instead we can use the so-called induction principle: Induction Principle.Assume thatkis an integer andP(n) is a proposition for allnk. (1) Suppose thatP(k) is true, and (2) for any integermkfor whichP(m) is true,P(m+ 1) is true.

ThenP(n) is true for all integersnk.

The induction principle can be compared to an innite sequence of dominos tiles, num-

bered 1,2,3, etc.1 2 3 4 5 6 7If them-th domino tile falls, it will hit the (m+ 1)-th domino tile and the (m+ 1)-th

domino tile will fall as well. If the rst domino tile falls, thenalldomino tiles will fall down.

(HereP(n) is the statement:\then-th domino tile falls down")1 2 3 4 5 6 7Since the induction principle is intuitively clear, we will simply accept it without proof.

This is why it is called an axiom. (We cannot formally prove the induction principle without making other, similar assumptions.) A typical example of the induction principle is the following:

Example1.1.Prove that

(1) 1 + 2 + 3 ++n=n(n+ 1)2 for every positive integern. Proof.We prove (1) by induction onn. Forn= 1 we check that 1 =

1(1 + 1)2

3

Suppose that (1) is true forn=m. Then

1 + 2 ++m+ (m+ 1) = (1 + 2 ++m) + (m+ 1) =

m(m+ 1)2 + (m+ 1) =(m+ 1)(m+ 2)2 so (1) is true forn=m+ 1. Now (1) is true for all positive integersnby the induction principle. Remark1.2.When the German mathematician Carl Friedrich Gauss (1777{1855) was

10 years old, his school teacher gave the class an assignment to add all the numbers from 1

to 100. Gauss gave the answer almost immediately: 5050. This is how (we think) he did it: Write the numbers from 1 to 100 from left to right. Write under that the numbers from 1 to 100 in reverse order.

1 2 3100

100 99 981101 101 101101|{z}

100
Each of the 100 column sums is 101. This shows that

2(1 + 2 ++ 100) = 100101

and

1 + 2 ++ 100 =1001012

= 50101 = 5050: This easily generalizes to a proof of (1). Gauss' proof can be graphically presented. For example, to see that

2(1 + 2 ++ 10) = 1011;

look at the following picture:1 2 3 4 5 6 7 8 9

10 12345678910

1011
A formula similar to (1) exists for the sums of squares, namely (2) 1

2+ 22++n2=n(n+ 1)(2n+ 1)6

Example1.3.Give and prove a formula for

1

3+ 23++n3

4 We have seen similar examples, namely (1) and (2). We can also add the formula 1

0+ 20+ 30++n0=n:

Let p k(n) = 1k+ 2k+ 3k++nk wherek2N. The examples so far suggest thatpk(n) is a polynomial of degreek+1 (and that the leading coecient is

1k+1). Let usassumethatp3(n) is a polynomial of degree 4. Since

p

3(0) is an empty sum, we have thatp3(0) = 0. We can writep3(n) =an4+bn3+cn2+dn.

for certain real numbersa;b;c;d. We have (3) n

3=p3(n)p3(n1) =a(n4(n1)4)+b(n3(n1)3)+c(n2(n1)2)+d(n(n1)) =

=a(4n36n2+ 4n1) +b(3n23n+ 1) +c(2n1) +d= =n3(4a) +n2(6a+ 3b) +n(4a3b+ 2c) + (a+bc+d) Comparing coecients in (3) gives us the linear equations:

1 = 4a(4)

0 =6a+ 3b(5)

0 = 4a3b+ 2c(6)

0 =a+bc+d(7)

We solve the system of equations and nda=14

,b=12 ,c=14 andd= 0. We now should conjecture the following formula: 1

3+ 23++n3=14

n4+12 n3+14 n2: Finding this formula was the hard part. It is now not so hard to prove this formula by induction:

Proof.We will prove that

(8) 1

3+ 23++n3=14

n4+12 n3+14 n2: by induction onn. The casen= 0 is clear, because both sides of the equation are equal to

0. If (8) is true forn=m1, then

1

3+ 23++ (m1)3=14

(m1)4+12 (m1)3+14 (m1)2:

From this follows that

1

3+ 23++ (m1)3+m3=14

(m1)4+12 (m1)3+14 (m1)2+m3= 14 (m44m3+ 6m24m+ 1) +12 (m33m2+ 3m1) +14 (m22m+ 1) +m3= 14 m4+12 m3+14 m2; so (8) is true forn=m. By induction follows that (8) is true for alln2N.

Notice that

14 m4+12 m3+14 m2= (12 n(n+ 1))2 which leads to the following aesthetic formula: 1

3+ 23++n3= (1 + 2 ++n)2:

5

Example1.4.What is the value of

112+123+134+?

Let us compute the partial sums. Perhaps we will nd a pattern.

112+123=26

+46
=23

112+123+134=23

+112
=812 +112
=912 =34

112+123+134+145=34

+120
=1520 +120
=1620 =45

A pattern emerges. Namely, it seems that

(9)

112+123++1n(n+ 1)= 11n+ 1:

Proof.By induction onnwe prove:

(10)

112+123++1n(n+ 1)= 11n+ 1:

Forn= 1 we check112= 112

If (10) is true forn=m, then

112+123++1m(m+ 1)+1(m+ 1)(m+ 2)=

11m+ 1+ (1m+ 11m+ 2) = 11m+ 2:

Hence (10) is true forn=m+ 1. By induction, (10) is true for all integersn1. We have

112+123+134+= limn!111n+ 1= 1:

Example1.5 (UMUMC, 1988).LetSnbe the set of all pairs (x;y) with integral coor- dinates such thatx0,y0 andx+yn. Show thatSncannot be covered by the union ofnstraight lines.

First we should try a few small cases, sayn= 0;1;2;3;4:n=0 n=1 n=2 n=3 n=4Notice thatSnis a subset ofSn+1. This will be helpful for our induction proof:

6 Proof.We prove the statement by induction onn, the casen= 0 being trivial. Suppose that one needs at leastn+ 1 lines to coverSn. DeneCn+1=Sn+1nSn. The setCn+1 consists ofn+ 2 points on the linex+y=n+ 1. Suppose thatklines`1;`2;:::;`kcover S n+1. case 1:One of the lines is equal to the linex+y=n+ 1. Without loss of generality we may assume that`kis equal to the linex+y=n+1. Then`1;`2;:::;`k1coverSnbecause k\Sn=;. From the induction hypothesis follows thatk1n+ 1, sokn+ 2. case 2:None of the lines are equal to the linex+y=n+1. Then each of the lines intersects the linex+y=n+ 1 in at most one point, and therefore it intersects the setCn+1in at most one point. SinceCn+1hasn+ 2 elements, there must be at leastn+ 2 lines. So in both cases we conclude that one needs at leastn+ 2 lines to coverSn+1.

2. Strong Induction

The following example illustrates that sometimes one has to make a statement stronger in order to be able to prove it by induction.

Example1.6.Prove that

12 34
56

999;9991;000;000<11000

Since 1000 =

p1;000;000 one might suggest that (11) 12 34
56

2n12n<1p2n

for alln1. Let us try to prove (11). We can check (11) for smalln(which gives some validity to our conjecture that this inequality holds). Suppose that (11) holds forn=m: (12) 12 34
56

2m12m<1p2m

We have to prove (11) forn=m+ 1:

(13) 12 34
56

2m+ 12m+ 2<1p2m+ 2:

If we divide (13) by (12) we obtain

(14)

2m+ 12m+ 2r2m2m+ 2:

If (12) and (14) are true, then (13) is true. By squaring (14) we see that (14) is equivalent to2m+ 12m+ 2 2

2m2m+ 2

and to (15) (2m+ 1)2(2m+ 2)(2m) So if (15) is true then our induction proof is complete. Unfortunately (15) is not true and we are stuck. Sometimes it is easier to prove astrongerstatement by induction: 7

Proof.We prove

(16) 12 34

2n12n<1p2n+ 1

by induction onn. The casen= 1 is clear because 12 <1p3

Suppose that (16) is true forn=m:

(17) 12 34

2m12m<1p2m+ 1

Since (2m+ 1)(2m+ 3) = (2m+ 2)21<(2m+ 2)2 we have that

2m+ 12m+ 2

2 <2m+ 12m+ 3 and (18)

2m+ 12m+ 2

Multiplying (17) by (18) yields

(19) 12 34

2m+ 12m+ 2<1p2m+ 3;

so (16) is true forn=m+ 1. This shows that (16) is true for all positive integersn. In particular, forn= 500;000 we get 12 34

999;9991;000;000<1p1;000;001<11000

Below is a trickier proof of Example 1.6.

Proof.Let

A=135999;9992461;000;000

and

B=2461;000;0003571;000;001:

ClearlyA < Bbecause

12 <23 ;34 <45

It follows that

A

2< AB=11;000;001<11;000;000

andA <10001. Example1.7.Prove that every integern2 is a product of prime numbers. 8

Proof.LetQ(n) be the statement:

\every integerrwith 2rnis a product of prime numbers." We use induction onnto prove thatQ(n) holds for all integersn2. Forn= 2 the statement is true because 2 is a prime number. Suppose thatQ(m) is true. We will proveQ(m+1). Suppose that 2rm+1. Ifrmthenris a product of prime numbers becauseQ(m) is true. Suppose thatr=m+ 1. Ifm+ 1 is a prime number, then m+ 1 is a product of prime numbers and we are done. Otherwise,m+ 1 can be written as a productabwith 1a;bm. BecauseQ(m) is true, bothaandbare products of prime numbers. Hencem+ 1 =abis a product of prime numbers. We have shown thatQ(n) holds for alln2. In particular, every integerr2 is a product of prime numbers becauseQ(r) is true.

3. Induction in denitions

We can also use induction in a denition. For example, the Fibonacci numbers is a sequence of numbersF0;F1;F2;:::dened byF0=F1= 1 and F n+1=Fn+Fn1; n1: By (strong) induction onnwe can prove thatFnis well-dened for all integersn0. The rst few Fibonacci numbers are:

1;1;2;3;5;8;13;21;34;55;89;:::

The sum notation is an example of a recursive denition. Suppose thatf(n) is some function. Ifa;bare integers andab+ 1 then we dene b X n=af(n) as follows. a1X n=af(n) = 0 and (20) bX n=af(n) =f(b) +b1X n=af(n) ifba.

One can then formally prove by induction that

c X n=af(n) =bX n=af(n) +cX n=b+1f(n): ifa;b;c2Zanda1bc. (Induction onc. Start withc=b.)

Similarly we have the product notation.

a1Y n=af(n) = 1 9 and bY n=af(n) =f(b)b1Y n=af(n): ifba. For nonnegative integersmandnwithmnwe dene a binomial coecient by n m=1 ifm= 0 orm=nn1 m1+n1 mif 0< m < n: If we arrange the binomial coecients in a triangular shape, we get Pascal's triangle: 0 0 1 0 1 1 2 0 2 1 2 2 3 0 3 1 3 2 3 3 4 0 4 1 4 2 4 3 4 4

After evaluating the binomial coecients we get:

1 1 1 1 2 1

1 3 3 1

1 4 6 4 1...............

4. Exercises

Exercise1.1.* Prove that

1

2+ 22++n2=n(n+ 1)(2n+ 1)6

for all positive integersn.

Exercise1.2.* Show that

112
+13 +12n112n=1n+ 1+1n+ 2++12n for alln2N.

Exercise1.3.* Prove that

nX i=0 m+i m =m+n+ 1 m+ 1 for all nonnegative integersmandn.

Exercise1.4.* Prove that

(a+b)n=n 0 a n+n 1 a n1b+n 2 a n2b2++n n b n: 10

Exercise1.5.*

(a) Prove that

1 +x+x2++xn=xn+11x1:

for every real numberxand every positive integern. (b) Ifxis a real number withjxj<1 then

1 +x+x2+=11x:

Exercise1.6.* Show that the sum of the squares of two consecutive Fibonacci numbers is again a Fibonacci number. Exercise1.7.** Cut out a 11 corner of a 2n2nchess board (n1). Show that the remainder of the chess board can be covered with L-shaped tiles (see picture).2 2 11 1

1The casen= 2 is shown below.Exercise1.8.** Find and prove a formula for

1

4+ 24++n4:

Exercise1.9.** Show thatn

m =n!m!(nm)! as follows: Dene f(x) = (1 +x)n=n 0 +n 1 x++n n x n: and considerf(k)(0) (f(k)(x) is thek-th derivative off(x)).

Exercise1.10.** Prove that

pn < nX i=11pi <2pn for all integersn2.

Exercise1.11.** Dene a sequencea1;a2;:::bya1=52

andan+1=a2n2 forn1.

Give an explicit formula foranand prove it.

11 Exercise1.12 (Division with remainder).** Suppose thatnis a nonnegative integer, andmis a positive integer. Prove that there exist integersqandrwithn=qm+rand

0r < m.

Exercise1.13.** Give and prove a formula for

1123+1234++1n(n+ 1)(n+ 2):

Exercise1.14 (Expansion in baseb).*** Suppose thatnis a positive integer, andbis an integer2. Show that there exist an nonnegative integerm, and integersa0;a1;:::;am2 f0;1;2;:::;b1gsuch that (21)n=ambm+am1bm1++a0 andam6= 0. Moreover, show thatmanda0;a1;:::;amare uniquely determined byn. (We will write (amam1a0)bfor the right-hand side in (21)). Exercise1.15.*** Suppose thatnis a positive integer. Show that we can write n=Fi1+Fi2++Fik wherekis a positive integer, 1i1andijij1+ 2 forj= 2;3;:::;k. Also show thatk andi1;:::;ikare uniquely determined byn. Exercise1.16 (Putnam 1985, B2).*** Dene polynomialsfn(x) forn0 byf0(x) = 1, f n(0) = 0 forn1, and ddx (fn+1(x)) = (n+ 1)fn(x+ 1) forn0. Find, with proof, the explicit factorization off100(1) into powers of distinct primes. Exercise1.17 (Putnam 1987, B2).*** Letr,sandtbe integers with 0r, 0sand r+st. Prove thats 0 t r s 1 t r+1 s s t r+s =t+ 1(t+ 1s)ts rquotesdbs_dbs35.pdfusesText_40

[PDF] la gestion d'entreprise pdf

[PDF] montrer que n(n+1)(2n+1) est divisible par 3

[PDF] n^3-n est divisible par 6

[PDF] montrer que n(n+1)(n+2) est multiple de 3

[PDF] montrer que n^3-n est divisible par 3

[PDF] montrer que n(n 1)(n 2)(n 3) est divisible par 24

[PDF] الموقع الرسمي للتكوين المهن

[PDF] التكوين المهني بالمغرب

[PDF] ofppt sidi maarouf

[PDF] التسجيل في التكوين المهني

[PDF] ista meknes

[PDF] takwine

[PDF] rapport pisa 2016 france

[PDF] pisa classement

[PDF] pisa 2015 france