LSU Number Theory Lecture 04 sumprod

Summary

The video script delves into the formalization of mathematical sums and products, essential for abstract mathematics and programming. It explains the limitations of 'magic three dots' notation and introduces summation notation for precise mathematical arguments. The script covers recursive definitions, factorials, and the binomial theorem, providing proofs for various summation properties and the formula for geometric sums. It also explores permutations, Pascal's triangle, and concludes with a proof of the binomial theorem, emphasizing the importance of number sense and induction in mathematical proofs.

Takeaways

• 📚 The necessity of formalizing sums and products in abstract mathematics is highlighted, as traditional notation with 'magic three dots' is insufficient for precise mathematical reasoning and computer programming.
• 🔢 Summation notation is introduced as a way to express sums mathematically, allowing for proofs by induction and precise computation, which is not possible with informal notation.
• 📈 The concept of recursive definition is explained, which is fundamental in defining sums and is useful for proofs by induction.
• 🔄 The ability to split off the last term in a sum is a common technique used in working with sums and products.
• 📉 The definition of an empty sum is introduced, where a sum with a starting index greater than the finishing index is defined to be zero.
• 📚 The script discusses the translation of 'magic three dots' notation into formal summation notation, which can sometimes be challenging.
• 🔢 The proof of the summation formula for the sum of the first n integers using summation notation and induction is provided.
• 📈 Properties of sums, such as re-indexing and splitting or combining sums, are introduced with an example proof for re-indexing.
• 📉 The script explains how to encode sums in summation notation, especially when dealing with complex expressions.
• 🎓 The importance of number sense in recognizing patterns, such as squares and roots, is emphasized for number theory applications.
• 📘 The script covers factorials, binomial coefficients, and the binomial theorem, showing their definitions and the proof of the binomial theorem using induction.
• 📙 The concept of Pascal's triangle is introduced as a visual representation of binomial coefficients and its relation to the binomial theorem.
• 🔑 The script also touches on the proof that binomial coefficients are natural numbers and the properties of sigma functions in rearranging terms of sums.

Q & A

Why is it necessary to formalize sums and products in advanced mathematics?

Formalizing sums and products is essential because the 'magic three dots' notation used in basic calculus has limited applicability and cannot be used for precise mathematical arguments or programming computations.

What is the significance of summation notation in programming?

Summation notation allows for mathematically correct arguments for sums and products, which can then be used to program computations accurately, unlike the ambiguous 'magic three dots' notation.

Can you explain the recursive definition of a sum?

A recursive definition of a sum starts by defining the sum for the simplest case (e.g., sum from J=1 to 1) and then defines the sum for subsequent cases by adding the next term to the previously defined sum (e.g., sum from J=1 to n+1 is the sum from J=1 to n plus the term at J=n+1).

What is an empty sum in mathematics, and what is its value?

An empty sum occurs when the starting index of a sum is greater than the finishing index. By definition, an empty sum is equal to zero.

How can the summation notation be used to express a sum with a given pattern?

Summation notation can express a sum by defining the index of summation, the starting and ending values of the index, and the formula for each term in the sum. This allows for a clear and unambiguous representation of the sum.

What is the difference between the summation of the first n integers and the sum using 'magic three dots'?

The summation of the first n integers uses a clear formula (n*(n+1))/2, whereas the 'magic three dots' notation lacks precision and does not provide a formula for calculating the sum, especially when the number of terms is not explicitly given.

How can you prove properties of sums using induction?

Properties of sums can be proven using induction by establishing a base case and then using the induction hypothesis to prove the property for the next case, often by reindexing sums or breaking them up and combining them in a way that demonstrates the property holds.

What is the formula for the sum of a geometric series, and how is it derived?

The formula for the sum of a geometric series is derived by considering the sum S = 1 - q^(n+1) and then using the properties of sums to show that S can be expressed as a fraction (1 - q^(n+1)) / (1 - q), where q is the common ratio of the series.

What is a factorial, and how is it defined mathematically?

A factorial, denoted as n!, is the product of all positive integers from 1 to n. It is defined mathematically as the product of n down to 1, and by convention, 0! is equal to 1.

What is the binomial theorem, and how does it relate to Pascal's triangle?

The binomial theorem states that (a + b)^n is equal to the sum of n choose k * a^k * b^(n-k) for k from 0 to n. It relates to Pascal's triangle because the coefficients of the terms in the expansion are the binomial coefficients, which form the triangle.

Outlines

00:00

📚 Introduction to Summation and Product Notation

This paragraph introduces the need for formalizing mathematical sums and products beyond the basic understanding from calculus. It highlights the limitations of the traditional notation with 'magic three dots' and emphasizes the utility of summation and product notation in creating mathematically rigorous arguments and programming computations. The paragraph also touches on factorials and the binomial theorem, setting the stage for a deeper exploration of these concepts. The recursive definition of a sum is explained, and the concept of an empty sum being equal to zero is introduced.

05:01

🔢 Summation Notation and Its Applications

The paragraph delves into the specifics of summation notation, explaining how to express sums with varying starting indices and how to handle empty sums. It provides examples of summation expressions and illustrates the process of translating sums from 'magic three dots' notation to formal summation notation. The paragraph also discusses the properties of sums, such as reindexing and splitting or combining sums, and includes a proof of the summation formula for the sum of the first n integers using induction.

10:03

📈 Advanced Summation Techniques and Proofs

This section explores more advanced techniques in summation, including the use of bijections to rearrange terms in a sum and the concept of telescoping sums. It presents a formal proof for the property of sums that allows for arbitrary reordering of terms, using induction and the concept of a bjective function. The paragraph also covers the proof of the formula for geometric sums and introduces the idea of summing sums, demonstrating how to break up or combine these expressions with proofs.

15:05

📘 Transition to Product Notation and Factorials

The focus shifts to product notation and its similarities to summation, with an emphasis on the properties of multiplication. The paragraph defines the product index, empty product, and factorials, explaining their mathematical significance and how they are used in calculations. It also introduces binomial coefficients and proves that the quotient in the binomial coefficient formula results in a natural number, setting the stage for further exploration of combinatorics.

20:07

🎲 Pascal's Triangle and Binomial Theorem

This paragraph discusses Pascal's triangle and its connection to the binomial theorem. It explains the concept of binomial coefficients and how they are derived from factorials. The paragraph presents a proof that the sum of two adjacent binomial coefficients equals the next coefficient in the sequence, which is a fundamental property of Pascal's triangle. It also connects this property to the process of expanding binomials, leading to the binomial theorem.

25:10

📚 Proof of the Binomial Theorem and Conclusion

The final paragraph provides a comprehensive proof of the binomial theorem using induction. It explains the process of expanding (a + b)^n and shows how the binomial coefficients arise from the sum of specific terms. The proof involves reindexing sums, applying Pascal's triangle, and demonstrating the pattern that leads to the binomial theorem's formula. The paragraph concludes with a summary of the importance of understanding these mathematical concepts and proofs for dealing with complex sums and products.

Keywords

💡Abstract Mathematics

Abstract mathematics refers to a higher level of mathematical reasoning that often deals with concepts that are not directly related to physical objects or practical applications. In the context of the video, abstract mathematics is the focus as the script delves into formalizing sums and products beyond the 'magic three dots' used in basic calculus. The theme of the video is to understand and formalize these concepts to create mathematically rigorous arguments.

💡Summation Notation

Summation notation is a method used in mathematics to express the sum of a sequence of terms in a concise form. The script discusses the need to formalize sums using summation notation, which is essential for creating mathematically correct arguments and for programming computations. An example from the script is the sum J = 3 to 5 of J * Jus 1, which is calculated using summation notation to be 38.

💡Recursive Definition

A recursive definition is a method of defining a sequence or series where each term is defined in terms of the previous ones. The script introduces the concept of a recursive definition when explaining how to define the sum of a series, which is crucial for proofs by induction, a common technique in mathematics.

💡Factorials

Factorials are a mathematical concept where the factorial of a non-negative integer n is the product of all positive integers less than or equal to n. The script mentions factorials as a topic that needs to be understood, as they are fundamental in various mathematical applications, including the binomial theorem discussed later in the video.

💡Binomial Theorem

The binomial theorem is a key concept in algebra that provides a way to expand expressions of the form (a + b)^n. The video script discusses the importance of understanding the binomial theorem, as it is a tool used in various mathematical applications. The theorem is proven in the script using induction, showcasing its significance in the study of abstract mathematics.

💡Induction

Induction is a method of mathematical proof, typically used to establish that a given statement holds for all natural numbers. The script frequently refers to proofs by induction, such as proving the summation formula for the first n integers and the binomial theorem, highlighting its importance in abstract mathematical reasoning.

💡Empty Sum

An empty sum is a sum where the starting index is greater than the finishing index, which by definition is set to be zero in mathematics. The script explains the concept of an empty sum when discussing summation notation, emphasizing the importance of formalizing mathematical concepts even for cases that may seem trivial.

💡Geometric Sums

Geometric sums refer to the sum of a geometric series, where each term is a constant multiple of the previous term. The script discusses the formula for the summation of geometric sums, demonstrating how mathematical notation can be used to express and prove properties of such series.

💡Bijective Function

A bijective function, also known as a one-to-one correspondence, is a function that is both injective (one-to-one) and surjective (onto). The script mentions bijective functions in the context of rearranging the terms of a sum, showing that the sum remains unchanged under such transformations, which is a fundamental property in the study of abstract mathematics.

💡Pascal's Triangle

Pascal's triangle is a triangular array of numbers where each number is the sum of the two numbers directly above it. The script connects Pascal's triangle to the binomial coefficients and explains how it is used to generate the coefficients in the binomial theorem, illustrating the visual and practical aspects of abstract mathematical concepts.

💡Binomial Coefficients

Binomial coefficients, often represented as 'n choose k', are numbers that represent the number of ways to choose k elements from a set of n elements without regard to the order. The script defines binomial coefficients in the context of factorials and uses them in the proof of the binomial theorem, showing their relevance in combinatorics and algebra.

Highlights

The need to formalize sums and products in abstract mathematics beyond the use of 'magic three dots'.

Limitations of 'magic three dots' in expressing sequences for computational purposes.

Summation and product notation allows for mathematically correct arguments and programming computations.

Recursive definition of sums and its accessibility to proofs by induction.

The concept of empty sums and their definition as zero in mathematics.

The challenge of converting sums expressed with 'magic three dots' into summation notation.

Encoding sums in summation notation with alternating signs and roots as an example.

Importance of number sense in recognizing patterns like squares and roots in number theory.

The summation formula for the sum of the first n integers and its proof using induction.

Properties of sums, including re-indexing and splitting or combining sums.

Proof of the formula for geometric sums using telescoping sums.

The use of bijections in rearranging the terms of a sum.

Defining factorials and their role in Pascal's triangle and the binomial theorem.

Proving that binomial coefficients are natural numbers using factorials.

Pascal's triangle and its connection to the binomial theorem through the addition of adjacent numbers.

The binomial theorem and its proof by induction, involving the expansion of (a + b)^n.

The importance of practice in working with induction for dealing with complex sums.

Transcripts

as we go deeper into abstract

mathematics we need to formalize sums

and products beyond what you may have

seen in the Calculus class where you use

what I would always call Magic three

dots to say how a sum goes on and uh

well one of the first things that you

would then ask yourself is why do we

need to formalize sums and products well

the thing is that these magic thre dots

that we use in sums um are just have

limited limited range basically

and they're usess for programming right

I can't give a computer the first couple

of terms of a sequence and put three

dots in there and the computer somehow

gives me the sequence so sumon product

notation allow us to produce

mathematically correct Arguments for

sums and products and uh we can also use

that notation to then program the

computations if necessary which is

something that we cannot do with the

magic 3 dots we'll also talk about

factorials and the binomial theorem here

because we just well we need to get used

to factorials and the binomial theorem

is something that well every so often we

will need it and and when you need it

you just are lost without it so we might

as well knock it out right here okay so

the definition of a sum is for every J

we let AJ be a number and we Define the

sum of AJ where J goes from 1 to one to

be

A1 and for n element n we Define the sum

from J = 1 to n plus one of of the AJ to

be the sum Jal 1 to n of the AJ plus the

N plus first term so this is what is

called a recursive definition this is

the kind of thing that is accessible to

proofs by induction which is really nice

one of the standard tricks that you are

going to see working with sums as well

as with products is this exactly this

splitting off the last term and uh well

the sum the parameter is also called the

summation index here and uh sums where

the starting index is greater than one

are defined similarly you just have the

sum jals K to K being a k and then from

K to n+1 you define recursively as is

done over here uh for example well the

sum J = 3 to 5 of J * Jus 1 well that's

3 * 2 right for J = 3 + 4 * 3 for J = 4

+ 5 * 4 for J = 5 so that would be 6 +

12 + 20 that ought to be 38 yes and uh

well then if you write the sum

differently if you take the sum J = 5 to

3 J * Jus 1 that's zero because

basically a sum in which the starting

index is greater than the finishing

index that is something that in

mathematics we call an empty sum in an

empty sum is set is defined to be zero

and what else do we have if I take the

sum J equals = 3 3 to 3 J * Jus 1

that'll be 3 * 2 and that's 6 Ah that's

not hard but this is what often is

problematic with magic 3 dots because

with magic 3 dots the sum would be 3 * 2

+ 4 * 3 plus dot dot dot plus n * n

minus one where n is three so then what

what happens with the four * 3 well it's

not there and in summation notation that

is really uh expressed that way too now

one of the things that we then want to

be able to do is we want to be able to

encode sums in summation notation and uh

if a sum like this for example is given

with the magic three dots we need to

write that in summation notation that

that can be hard and it can be easy this

one is an easy one I think because every

term is of the form number divided by

the next number right it's 2 over 3 3

over 4 4 over 5 okay and we start at two

sure because we start with 2 over 2 + 1

we end at 14 because we end up with 14 +

14 over 1 and so that means that the sum

is the sum JAL 2 14 J over J + 1 if you

want to write the sum 1 - < tk2 + 3un of

9 - 4 root of 64 plus 5ifth root of 625

minus 6th root of

7,776 in summation notation well that's

when you may want to have somebody else

do it but that's not an option

uh because you're supposed to do your

own homework so let's take a look at

that we've got alternating signs here

right and so every term is therefore of

the form negative 1 to the J negative 1

to the J always encodes alternating

signs right but the first term is

positive and so negative 1 to the 1

would be negative so it's actually

negative 1 to the J + 1 so sometimes you

just you write down what you need and

then you adjust that's one of the ways

to deal with these things times some

thing and we're always taking the jth

root right we're taking the first root

of this one the second root of that one

the third root the fourth root the fifth

root the sixth root and so on so now we

still need to figure out what that is

here inside the root well what's inside

the root it's

one it's two it's 9 it's 64 okay so 9 is

3 squar 64 is 4 cubed 2 is 2 to the 1st

625 is 25 s is 5 to the 4th Okay so goes

1 2 3 4

5 but it's not 5 to the 5th it's 5 to

the 4th it's 4 to the 3r it's 3 squar

it's 2 to the 1st and then here uh one

to the zero actually is is one and this

wi once you check it this actually is 6

to the 5th and so that means the three

dots here and and those are not three

dots that say oh well you know you're

you're doing something I just needed a

placeholder that is J to the J minus one

and that means when we start with 1 and

we finish with six the sum of these

things is the sum J = 1 to 6 -1 to the J

+ 1 J to the J minus one/ J okay so you

want to get your number sense back to

the point where you can factor numbers

where you can recognize squares and

things like that because every so often

you really do need that in number

Theory um okay

so let's revisit the summation formula

that we had in the induction

presentation of the sum of the first n

integers which is n n + one well if I

want to prove that that's the case with

summation notation I still use induction

it's a base step but the base step now

is that the sum Jal 1 to one of J is 1

and that's 1 12 1+ 1 so that's right and

so everything is is completely

unambiguous here the induction step in

going to n plus one is that we take the

sum J = 1 to n + 1 of J and we know that

that's a sum J 1 to n of J plus n + 1 by

itself by induction hypothesis we know

that this is n n + 1 plus n + 1 is kept

and uh well then I just factor out the N

plus 1 so I get n + 1 * n + 1 and that's

n + 2 / 2 * n + 1 and that is nothing

but this n + one put here and the n + 2

turned into n + 1 + 1 sorry the

highlighting sometimes doesn't work too

well on these slides but either way this

is the induction proof of the summation

formula for the first in integers now uh

we can also prove properties of sums now

so for example if AJ and BJ are numbers

then we have the following we've got

that the sum J equals 1 to in aj+ K is

the sum I equals k + 1 to k + n of a I

so that's this re indexing of sums that

you may have seen in a differential

equations class when you solve

differential equations with SE with

series or with the method of

fenus uh we also have that as long as m

is smaller than n we can break up a sum

in the middle or combine them so the sum

J = 1 to M of AJ plus the sum j = m + 1

to in of the AJ is just the sum Jal 1 to

in of the AJ and we're going to prove

only part one here so let's see base

step if you've got the sum J = 1 to n j

= 1 to 1 of A J + K well then that is A1

Plus K and that's a k + 1 and that's the

sum I equals k + 1 to k + one of a I so

that that's not that bad induction Step

n to n+ 1 well you take the Su J = 1 to

n+ 1 A J +

K and you know that that's the sum Jal 1

to n a j plus K plus the last term split

off which is a in plus one quty plus K

and I can just shift the plus one around

right so and okay so by induction

hypothesis I know that the first sum is

the sum IAL k + 1 to K plus n of a i and

in the second term I just shift the plus

one or I just commute the index here

yeah I just say that this is a K plus n

plus

one and uh well of course that then is

the sum I equal k + 1 to k+ n + 1 of the

AI and uh that's the proof of

that uh we can also then use summation

notation to prove something like the

formula for geometric sums that's an

application of what we've just done

because if I have 1 minus Q to the n + 1

well that is just the sum i = 0 to n q

to the I minus the sum I = 1 to n +1 Q

to the I these setups here are also

called telescoping sums because

basically what happens is the sum the

terms IAL 1 I 2 all the way through IAL

n cancel between these two the only

terms that survive are the term I equals

0 which is the one and the term IAL n+ 1

which is the Q to the n+ one

right but these sums I can now go ahead

and rewrite I keep the first sum with

just an index I equals J so this is

still the sum J equals 0 to n q to the J

but here I'll I'll shift the index and I

shift the index backwards so this is is

well this sum starts with Q to the 1 and

ends with Q to the n + 1 this sum starts

with Q to the 0 + 1 which is Q to the

1st and it ends at n with Q to the n +

one so this sum and that sum are the

same and now well now I can factor out a

q out of the latter sum here right and

so that gives us sum Jal 0 to NQ to the

J minus Q * the sum Jal 0 to n q to the

J and that's 1 - Q * the sum Jal 0 to n

q to the J

and now I can just solve for the sum Jal

0 to the N to n q to the J and that's 1

minus Q to the n + 1 over 1 minus q and

that's the formula for the summation of

geometric sums what else can I do uh

well we can again take numbers AJ and

BJ and if Sigma is a bjective function

so it's a function that is one to one

and on to from the index set to itself

so this is something that just basically

rearranges the terms where well then you

can rearrange the terms of the sum uh

you can also take a sum that is a sum of

sums of terms and break up the sum and

again we're only going to prove the

first part and I think this is where

this presentation is coming out of

another class actually where we are a

little bit more formal so this proof

definitely is a bit on the formal side

for this number Theory class but we

might have as well work our way through

it why is it all right to reorder the

sums in an arbitrary way in a a sum that

is arbitrarily long of course our

feeling for numbers tells us that ought

to be the case right I mean 3 + 5 is 5 +

3 we've known that forever and that

should work the same way if we've got

25,000 terms or so but we can formally

prove that uh the summation as defined

actually has this property so let's take

a look at that the base step is quite

trivial because if n is equal to one

well how many ways can you rearrange one

object you can arrange it in one way

only and so there's nothing to be done

if you take the induction step from n to

n+ one well that's where you take this

bcor function there's reordering of the

index sets and you take that to be

arbitrary and well if the end term stays

where it was then the whole thing isn't

that bad because then the sum J equals 1

to + 1 a sigma of J is the sum J = 1 to

n a sigma of J plus a n + 1 CU a n + 1

is a sigma n plus one right and then I

know that this one here by induction

hypothesis is the sum Jal 1 to n AJ plus

the a n+ 1 from the previous one and

then by definition that is just the sum

J = 1 to n + one of the a

subj all right however if this is a

little bit more complicated if the N

plus first term is actually scrambled

into the first in terms so if Sigma n +

1 is less than or equal than n then I

let I to be exactly that place where the

N plus first term goes and I argue as

follows I take the sum Jal 1 to n plus 1

a sigma of J and that's the sum J = 1 to

i - 1 a sigma J plus a sigma I plus the

sum j = i + 1 2 N +1 a sigma of

J and uh well now I know because uh

numbers commute I can put the sigma of I

to the end right so that's that's all

that's been done here and then I know

that this one here Sigma of I was n plus

one so a sigma of I is a n + one and I

can also I kept the first summand and I

can reindex the sum so now this is the

sum Jal I to n a sigma of J + 1

but that is now basically saying that my

first J numbers are being mapped to

Sigma of J which is within the set 1

through n and the numbers after I are

being mapped to Sigma of J + one which

is also in one through in and so that is

now just another bjective function from

the set one through in to itself I call

that thing to and so to of J is Sigma of

J as long as we're below I and to of J

is Sigma of J + 1 once we are passing I

and so that's just the sum Jal 1 to n a

tow of J plus a n + 1 and we know that

that is the sum Jal 1 to n + 1 A J

because this to here is doing not doing

anything this is the sum Jal 1 to n a j

okay that one was a little bit of a side

step into permutations that is something

that I don't think we'll be messing with

too much but basically is one of those

if you can follow something like this

the rest shouldn't be that bad okay so

what else can we do if I take numbers

and if I take a sum where every number

is multiplied by the same number well

then I can factor out that number that

proof is a really nice exercise I

certainly recommend that to you if you

want to practice induction but we move

on products for products I don't think

we are going to prove that many

statements but basically what we should

realize here is that even though

products aren't something that we have

commonly worked with that much in

calculus uh they work just like sums

only that we have to work with the

vagaries of multiplication rather than

addition so let the ajs be numbers I

Define the product J equals 1 AJ to be

A1 I Define the product for JAL 1 to n +

one of the ajs to be the product Jal 1

to n of AJ * a n + 1 the parameter is

the product index and uh yeah that's

just the product of these numbers right

and we Define the power a to the N to be

just the product Jal 1 to n of a with

itself and then also the empty product

we will run into that every so often so

if I have a product index where the

starting index is larger than the ending

index the empty products actually

assumed to be

one okay now we Define factorials

because we want to go into Pascal's

triangle and then ultimately the

binomial theorem for all natural num we

Define in factorial to be the product of

the first in integers that looks

different than what you may have seen

before with the magic three dots where n

factorial is n * n- 1 * nus 2 and so on

all the way down to one but this is the

same thing

right and we call that the factorial we

set Z factorial equal to 1 and that's

again if the starting index is greater

than the ending index and then an empty

product is set equal to 1 and we're also

defining binomial coefficients where

we're taking numbers in in subzero so

natural numbers or zero so that K is

less than or equal than n and we Define

the binomial coefficient as and this is

r n choose K it is n factorial / K

factorial time n minus K factorial it's

called n choose K because this is number

of ways you can choose K objects out of

n objects if the order of the objects

does not matter

okay now we need a little Lemma and uh

basically we're first going to prove

that the quotient in choose K is a

natural number well that ought to make

sense because if this interpretation is

correct if this is the number of ways

you can choose K object out of n objects

that's got to be an integer that's got

to be a natural number but how do you

prove that of the formula well it you

prove it in a way that gets us used to

working with factorials and that's

something that we need to do here also

so for all natural numbers we have that

in choose zero and in choose in are

nothing but in factorial divided 0

factorial over in factorial right if K

is zero it goes directly if K is n well

then the N factorial is on the left and

the zero is on the right but either way

you end up with n factorial over 1 * n

factorial and that's one so we only need

to consider a k between 1 and N minus

one and for that well in a base step for

n equals 1 we have that 1 choose 0 is 1

choose

one and they're both 1 factorial over 0

factorial * 1 factorial and uh that's

one but when we go from n to n+ 1 we let

K to be between 1 and N which is n + 1

minus

1 and we know that in choose K minus one

and in choose K are natural numbers that

is something that comes from the

induction hypothesis because we already

know that things work for n there's n

and that means that their sum is

contained in in okay so if the element

sign is flipped around that just means

that the natural numbers own this

number and we know that n choose K-1 is

n factorial over K-1 factorial time nus

K-1 quantity factorial and N chose K is

n factorial over K factorial / n minus K

factorial and now well now we need to

find a common denominator here because

we want to add these things up um and so

I need an extra

K and I need an

extra uh n- K minus one because n minus

quantity K-1 is n minus k + 1 actually

and so that means the first one is

expanded with K so we get a k factorial

here the N minus k + 1 factorial is n +

1 minus K factorial here right and uh

then the denominator that I need here is

I get the K factorial and if I need an

extra n + one minus K well I just put

that in there and I keep the N factorial

because we have a common denominator K

factorial n + 1 minus K quantity

factorial we have uh we we can add the

two and so we end up with an N factorial

in the numerator that can be factored

out and we have a K plus the N minus one

n+ one minus K which we have here and of

course the K and the minus K cancel out

and that means we've got n factorial n+

one in the numerator and that's n plus1

factorial the denominator doesn't change

and now we realize that this is n plus

one choose K and so as we claimed for

any K between one and N we have that n

plus one choose K is an element of the

natural numbers okay so that's another

one of those proofs where you really

first have to follow the steps this is

how the logical argument would progress

right we first know this and then we

know everything else

um however you pretty much have to have

some kind of an incling that this

equation works and in fact this equation

is quite important it is called Pascal

triangle and that is that the equation

in choose K minus one plus n choose k

equal n + 1 choose K holds for all

natural numbers n and K with K smaller

equal than n and uh well the proof we

just gave the proof right the only thing

that is a little bit in doubt here is

why on Earth do you call that thing a

triangle because after all there is no

triangle here unless you start writing

it up here's in choose zero which is one

here's in choose okay here's zero choose

zero that's one one choose zero and one

choose one are both one one two choose

one uh two choose zero is one two choose

one is two there's one way to choose one

there are two ways to choose one object

out of two and then two choose two is

one again three choose one is one three

three choose zero is one three choose

one is three three choose two is three

three choose three is one and uh if you

keep going like that you realize that's

what you've learned in school to be

Pascal's triangle because that's how you

get the coefficients for multiplying out

binomials and how do you generate Pascal

triangles well you you always take the

sum of the two numbers that are adjacent

to the top to work things out and well

if this is n plus one choose K well then

n choose K is here and N choose K minus

one is here and the sum of these two has

to be n plus one choose K and so that's

exactly what is happening here so that's

why this is called Pascal's triangle

Pascal's triangle of course is connected

to the binomial theor and that's the

last thing we're going to prove here the

binomial theorem for any number a and

all natural numbers we have that a plus

b quantity to the N is the sum k equal 0

to n n choose k a to the k b to the N

minus K this is exactly what you've

learned in school you count up in the

powers of a you count down in the powers

of B the sum of the exponent must be in

and the coefficients come from Pascal

triangle but why is that true well again

we can prove it by induction and uh well

the base step is quite easy a plus b to

the 1 well that's a plus b and that's 1

choose 0 a to the 0 B the 1 minus 0 plus

1 choose 1 a to the 1 B2 1 minus one if

you really need to write it all up and

that is the sum k equal 1 k equals 0 to

1 1 choose k a to the k b to the 1 minus

K so that works out perfectly and the

induction step it's going to be a little

longer that's why we need a new panel

but if you take a plus b to the n+ 1

what's the standard trick you split off

the last term so this is A + B * a plus

b to the N we know what a plus b to the

N is by the binomial theorem and by the

uh induction hypothesis for the binomial

theorem so this is a plus b * the sum k

equal 0 to n n choose k a to the k b to

the N minus K all right now we can

multiply this out right so this is If I

multiply this uh a with the with the

summation I get sum k equals 0 to n n

choose k a to the k + 1 B to the N minus

K plus and If I multiply the B with that

thing I get sum k equal 0 to n n choose

k a to the k b to the N plus one minus K

all right so what do we have here in

this

one the powers look like they

should and in this one well in this one

they do not because you don't want to

have a K plus one and you don't want to

have an N minus K here you want to have

an N plus one so I've got to shift the

index in the first first sum and I can

do that if I shift up the index by one

so if I

say uh k equals J minus one well then I

get a j minus one here I get J minus one

+ one here so that's a j if K is J minus

one the minus minus one has to be

compensated and I get a plus one so that

works out too and if K is J minus one

well then J has to be one to get k

equals z to start and J has to run to n

plus1 to capture k equal n so that's how

I reindex that sum the other sum stays

the same now in order to add them I have

to split off the last term here and the

last term here is n choose n + 1 minus

one so n choose n a to the n + 1 B to

the n + 1 minus n plus one so that's uh

B to the zero plus in chose Zer I need

to split off the zeroth term here right

so in chose z a to the 0 B to the n + 1

minus 0 here plus the sum Jal 1 to n and

I'm just going to put everything

together because now you realize that

the powers here are the same so I can

Factor those out and so from the first

sum I get the in choose J minus one from

the second sum I get the N choose J and

the factored out powers are back here

now by Pascal's triangle I know that

that is n plus one choose J so that

means well the first one n choose n is

the same as n plus1 choose n plus1

everything else stays the same n choose

zero is the same as n plus1 choose Z

everything else stays the same and this

summation is the summation J = 1 to n n

+ 1 choose J A to the J B the n + 1

minus J and this term fits the pattern

for the zeroth term in this sum and this

term fits the pattern for the N plus

first term in this sum and so this is

nothing but the sum J equals 0 to n + 1

n + 1 choose J A to the J B to the n + 1

minus J and that is the end of the proof

of the binomial theorem all right so

here you had a bunch of examples of how

to work induction with sums and that is

also certainly important for us to work

with because every so often we will need

to deal with some summations it's a

matter of practice um as you also have

seen there are various degrees of

difficulties from the summation of the

first in integers which is a standard

example through the binomial theorem

which is an important theorem but where

the proof certainly gets a bit harder

all the way to that strange sum where I

talked about the sigma rearranging the

terms which is more on the abstract side

and well you want to be on top of all of

those reasonably well so that you can uh

so that it won't bother you when you

actually have to deal with a rather ugly

sum at some point in time okay with that

you get to the homework thanks