LSU Number Theory Lecture 04 sumprod
Summary
TLDRThe 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
đ 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.
đą 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.
đ 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.
đ 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.
đČ 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.
đ 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.
Mindmap
Keywords
đĄAbstract Mathematics
đĄSummation Notation
đĄRecursive Definition
đĄFactorials
đĄBinomial Theorem
đĄInduction
đĄEmpty Sum
đĄGeometric Sums
đĄBijective Function
đĄPascal's Triangle
đĄBinomial Coefficients
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
5.0 / 5 (0 votes)