Balancing Numbers

okay in this video we're gonna look at the notion of a balancing number so the definition goes like this we say in which is a natural number is called a balancing number with a balancer of R if the sum one plus two plus three all the way up to n minus one is equal to the sum n plus 1 n plus 2 all the way to n plus R so you can think that like our balances the numbers before in and a certain number of numbers after in when you sum them so I like to think about it with this picture so we've got this scale and is like in the middle of the scale so it's like the point of the teeter-totter and then we have this sum 1 plus 2 all the way up to n minus 1 has the same weight in other words it has the same sum as this sum n plus one up to n plus r ok so now that we have this picture let's look at some of the first examples of balancing numbers so the first example is 1 so I mean this is kind of a trivial example but it's generally agreed upon that we include 1 as a balancing number and here the balancer is like the number zero so notice we have the sum of everything smaller than 1 well that's just zero and the sum of zero numbers bigger than one so obviously we have zero equals zero so here if we're keeping a list here balancing numbers then the first one would be the number 1 and actually some people include zero as the first one but will not do that will include 1 as the first one to go with our definition that has to be a natural number okay so the next example would be 6 and that's because if we take 1 plus 2 Plus 3 plus 4 plus 5 notice that's equal to 15 but now 15 is the same thing as 7 plus 8 that's also 15 so we have the sum 1 2 5 is the same thing as the sum of 7 and 8 so in this case our R so our balancer is the number 2 because we need two numbers past 6 in order equal the sum of all of the natural numbers before six so that makes six our next balancing number okay so the next one after six is 35 and that's because one plus two plus three all the way up to 34 so you can easily check that that's equal to 595 and then you can also check that if you take 36 all the way up to 49 that is also equal to 595 and you might say well what's the balancer in this case well you can check that the balancer in this case is the number 13 and that's because we take 13 numbers over there on the right hand side okay good so that makes 35 the next balancing number okay so now what about the one after that so the one after that is 204 and you can check that if you take 1 plus 2 all the way up to 203 if you add all of those numbers together you'll get 20,000 706 okay good and then if you similarly take the sum 205 all the way up to 288 then you'll also get 20,000 706 and in this case you can check that your balancer is equal to the number 84 so we've got a new balancing number 204 and the balancer is 84 and so let's see we can add that to our list 204 as the next balancing number okay so now instead of like going on looking at examples of these balancing numbers what I'll do is I'll clean up the board and we'll work towards describing them in general okay so once we're called that we say in as a balancing number if the sum of the N minus 1 natural numbers smaller than n is the same thing as the sum of the are natural numbers larger than N and here R is equal to the balancer so let's go ahead and simplify this equation a little bit so notice that the left hand side is a triangular number and it's well known that those have a closed form and in fact we can take one plus two plus three all the way up to n minus one we can add that together and we'll get n times n minus 1 over 2 so there's a bunch of videos on YouTube where you can check that this is the closed form for a triangular number okay good now let's go ahead and look at the right hand side and see if we can simplify that as well so notice we'll take n plus 1 plus n plus 2 all the way up to n plus r and notice we can put all of the ends together so this is equal to n plus n all the way up and now how many ends are there there are exactly our ends and then after that we have 1 plus 2 all the way up to our great but now we can simplify this a little bit so notice that is going to be n times R that's actually exactly the definition of multiplication is repeated addition and then we have another triangular number here so we can use the formula for that as well so that's going to be R times R plus 1 over 2 okay good and actually since we want to set these equal to each other it's probably going to be useful to factor a 1/2 out of this to make that a little bit easier so let's go ahead and do that if we factor 1/2 out of this we can think of this term as having 2 over 2 in front of it so we're going to get 2 times n R plus r squared plus 1 so we get something like that so now we have this equation has to be equal to that equation so we're on track to being able to describe these balancing numbers okay I'll clean up the board and we'll look at that equation in a little more depth okay so I've moved the equation to the top of the board I've rearranged things a little bit and I've corrected a small typo that was on the last board so look for that if you're interested so we've got 1/2 times n times n minus 1 is the same thing as 1/2 times R squared plus 2 in R plus R so notice we can get rid of those 1 hats immediately just by multiplying this equation on the both sides by 2 and then that's going to give us the following equation so we have N squared minus N equals R squared plus 2 in R plus R and now we have two things that we can do we can maybe like use the quadratic formula to solve this for R or we can use the quadratic formula in order to solve this for N and in fact it's going to be most useful to use the quadratic formula to solve for R so let's go ahead and write this in a form that we can do that so we'll have R squared plus now we can factor an R out of this that'll leave us with 2n plus 1 times R and then we're gonna have this as plus n minus N squared equals 0 after we move this over to that side of the equation now we can use the quadratic formula in order to solve for R so notice that's going to give us R equals so we have negative the B term so that's going to be minus 2 n minus 1 and then plus or minus but I'll just say that we only need to keep the positive result because we're working over the natural numbers and that R is also a natural number in other words it can't be negative and if we let this be negative we will only have and the case when we have the negative will only give us negative numbers so we have plus the square root of so B squared so that's going to give us 2 n plus 1 squared minus 4 times a times C so that's going to be minus 4 times n minus N squared good so we've got something like that and then that's going to be all over 2 okay so now let's see if we can simplify this so that's going to give us minus 2 n minus 1 plus the square root of so notice if we multiply this out we're going to get 4n squared plus 4n plus one so that's what we get there and then if we distribute this minus four we get minus 4n plus 4n squared so notice the four ends cancel and we're going to get 8n squared plus 1 so we have 8n squared plus 1 all over 2 great now notice here we're taking the square root of an odd number we also have an odd number there the square root of an odd number if it is an integer will be odd so that means we'll have an odd number plus an odd number over two so this is always an integer in the special case when 8n squared plus 1 is a perfect square so we need like I said 8n squared plus 1 to be a perfect square and in fact every time that 8n plus 1 is a perfect square that makes R into a natural number which means we will have a balancing number and a balancer so let's just reiterate if 8 and squared plus 1 is a perfect square then n is a balancing number and r which is defined by that formula over there is its balancer ok so I'm going to move that to the top and then we'll talk about how to figure out what values of n arise from this situation ok so on the last board we got to this point in is a balancing number if and only if 8 n squared plus 1 is a perfect square in other words we can write 8 n squared plus 1 equals M squared for some natural number M so let's notice that we had our list of balancing numbers already and so notice if we have N equals 1 so that makes a n squared plus 1 equal to nine which is equal to three squared so we're good to go there so in other words the ordered pair M comma N equals 3 comma 1 is a solution to this equation and I should say the M part of the solution is not super important for our goal of finding balancing numbers but it is important for finding solutions to this equation ok and so now next if n is equal to 6 that makes 8 N squared plus 1 equal to 289 but that's equal to 17 squared so you can check that so remember n equal 6 was a balancing number and that corresponds to a solution to this equation of 17 comma 6 which again the M value of the solution is not really super important for the balancing numbers but it is important for solving this equation ok so now the next thing I want to do is move to classify the solutions to this equation so I'll clean up the board and then we'll get to that ok so along our goal we're going to look at the following claim so if X Y is a solution to this equation M squared minus 8n squared equals 1 now notice that's exactly the same as the equation M squared equals a squared plus 1 but this is going to be a more useful form for us and I should say that this is known as a quadratic Daiya fantine equation and equations like this were studied throughout the history of mathematics in fact the way that we're going to create new solutions was discovered by Brahma Gupta who was an indian mathematician okay so if X Y is the solution to this equation then so is X K Y K so that ordered pair where we define X K Y K in the following way so XK plus YK times root 8 is the same thing as X plus y times root 8 raised to the K power so some times this x and y are called the fundamental solutions and general it's kind of hard to find the fundamental solutions for equations like this but in our case we know them from looking at those balancing numbers earlier and I should say that we can equivalently define XK and YK by the following equation so we have XK minus YK root 8 is the same thing as X minus y root 8 raised to the K power so good so we're going to prove this by induction so notice our base case is pretty easy because that's just K equals 1 and we know that x squared minus 8y squared equals 1 so that is a solution to this equation ok so now we want to make our induction hypothesis which will be the K case is true in other words we will suppose that XK squared minus 8y k squared equals 1 and consider the following equation so we want to consider XK plus 1 squared minus 8y k plus 1 squared and we want to show that that's equal to 1 ok so now what we'll do is we'll factor this so notice we can factor this in the following way XK plus 1 plus YK plus 1 times root 8 times XK plus 1 minus YK plus 1 times root 8 ok good but now notice that by this equation we can write this in the following way so we can write this as X plus y root 8 times XK plus YK root 8 so that's what we can do to this first term good and then to the second term we can do something similar so this is X minus y root 8 and then this is XK minus YK root 8 good and now what we'll do is strategically recombine these so we'll combine this one with this one and then we'll also combine this one with this one and so notice combining the red ones will give us x squared minus 8y squared so that's what we get from combining the red ones and then combining the blue ones will give us X K squared minus 8y K squared good and now notice the red thing is equal to one by our setup because we're assuming that X Y is the solution to this and then the blue underline is equal to one because of our induction hypothesis so this is equal to one times one which is equal to one which means that XK plus 1 comma YK plus 1 is a solution to this equation which proves the claim and now something that's part of the claim which I won't prove which isn't written here is that all solutions to this equation are in this list generated by XK and YK ok so I'll clean up the board will state that and then we're almost to the point where we'll have a formula for these ok so on the previous board we proved that if x and y we're solutions to this quadratic daya Fantini equation then XK YK are also solutions and something I'm not proving but is a fact is that all solutions to this Diophantus Wagin are gotten from this formula ok good so now I want to play around with this formula a little bit to see if we can get a handle on what these numbers XK YK are so here's what we'll do so notice XK plus YK times root 8 so that's going to be equal to X plus y root 8 to the K power great but notice that that's equal to X plus y root 8 times X plus y root 8 to the K minus 1 power so that's easy to check but now notice that that's equal to X plus y root eight times X sub K minus one plus y sub K minus one times root eight because that's exactly how XK minus one and YK minus one are defined so now what we can do is foil this out and notice we'll get x times XK minus one and then we'll get plus eight times y times y K minus one now I'm going to put those in parentheses good so those are the parts that are not connected to root eight so I got that from multiplying this term in this term and this term in this term so now I look at what we get from the other terms and so notice that's going to give us plus X times YK minus 1 times root 8 good and then plus XK minus 1 times y times root 8 so I'll put those in blue okay good now what we can do is we can equate the stuff that I have in red on each side of the equation and the stuff that I have in blue on each side of the equation but not actually everything in blue just the stuff that is the coefficient of the square root of 8 and this has to do with the fact that since the square root of 8 is an irrational number and everything else is a natural number there's some sort of separation between these two types of terms so now notice that's going to give us the following formula so we'll have X K is equal to x times X K minus 1 plus 8 times y times y K minus 1 good and then we'll have also Y K is equal to x times y K minus 1 plus XK minus 1 times y and so now let's recall that we have a solution and that solution is X y equals 3 comma 1 and so we can check that so 3 squared is 9 minus 8 is 1 so that's a solution and then notice in this case the Y variable is giving us the balancing number so that's our x and y so we can take this which is like our starter solution and put it down here and notice that's going to give us X K equals 3 times X K minus 1 plus 8 times YK minus 1 so we have that nice recursion for X K and then we have a similar one YK equals YK minus 1 and that is times 3 plus XK minus 1 ok good so these are our recursions that will define these solutions XK and YK ok so I'll move that to the top and then we'll keep going okay so so far we've built up to the following fact so all solutions to M squared minus 8n squared equals 1 are in the sequence of ordered pairs X K Y K where I should say here x1 y1 equals 3 comma 1 and we have this nice recursion so XK plus 1 is 3 XK plus 8 YK and YK plus 1 is XK plus 3 y K okay good so now notice I've reindex these a little bit but that's just because it's kind of helpful for exactly what we're doing now the next thing I want to do is look at these one step lower so notice this is equivalent to X K equals 3 X K minus 1 plus 8 YK minus 1 and YK equals XK minus 1 plus 3 YK minus 1 so now what I want to do is I want to take this second equation and multiply it by three and then subtract it from the first equation and let's see the motivation here so let's recall that our Y part of this ordered pair gives us our balancing number which is that really our goal and so what we want to do is somehow combine these in a certain kind of way so that we have a recursion for the Y terms only in terms of the Y terms and not involving the X's as well so notice that's going to cancel out this x part so notice here we're going to have XK minus 3y K that's when we get on the left-hand side of the equation now we'll have three XK minus 1 minus 3 XK minus 1 and then we'll have 8 YK minus 1 minus 9 YK minus 1 so that's going to give us minus YK minus 1 ok great but now notice we can rearrange this a little bit and that allows us to write XK equals 3 YJ minus YK minus 1 now the next thing we want to do is take this value for XK and insert it into this recursion right here so let's see what we get when we do that so we have YK plus 1 equals 3 YK minus YK minus 1 and then plus 3y K so in other words we have 6 YK minus YK minus 1 and then recall that the Y parts we're giving us our balancing numbers so we have this two-step recursion for the balancing numbers so I'm going to clean up the board then I'll bring this to the top I'll rename these as balancing numbers and then we'll move on from there ok so let's see where we are I've renamed our balancing numbers from Y k's to be KS because now we're really back in the balancing number world and we are not worrying so much about that quadratic diet Pantene equation that we got so the cave balancing number BK is given by the following recursion so BK e equals six times the previous one BK minus one minus BK minus two and then let's recall we have our two seeds B 1 equals 1 and B 2 equals 6 which we got from playing around with that earlier so now what I want to do is find a closed formula for these and we'll do that via generating functions so let's go ahead and set capital B of X equal to the sum K equals 1 to infinity of BK times X to the K now I have a video will refine the generating function for the Fibonacci numbers previously and we'll use the same kind of strategy here so I want to take out the first two terms here so notice the first term is going to be 1 times X to the 1 in other words we'll have X and then the second term will be 6 x squared and so that's because B 1 is 1 and B 2 is 6 and then that's attached to the correct power of X and now we'll have this as plus the sum K equals 3 to infinity of BK X to the K now the next thing we want to do is apply the recursion to all of those leftover terms so that's going to give us x + 6 x squared plus the sum K equals 3 to infinity of BK minus 1 times 6 minus BK minus 2 times X to the K ok so now I'll go ahead and split that sum into two parts so we have X plus 6 x squared plus 6 times the sum K equals 3 to infinity of be K minus 1 times X to the K good and then minus the sum K equals 3 to infinity of k minus 2 times X to the K okay so now I'll go ahead and bring this up and then we'll keep going okay so I've brought my previous step to the top and I've also factored some X's and X Squared's out so we have B of X which is our generating function for these balancing numbers is given by X plus x squared plus 6x times this sum K equals 3 to infinity of BK minus 1 X to the K minus 1 and then minus x squared times the sum K equals 3 to infinity of BK minus 2 X to the K minus 2 so now we want to re-index these sums so that we can write them back in terms of the original generating function so here we will replace K with k plus 1 and here we'll replace K with k plus 2 so let's see what that does for us so we had these terms just to bring down so X plus 6 x squared plus 6 x times the sum K equals 2 to infinity of BK X to the K ok so that's what we get for that one so notice we had to change our starting point from 3 to 2 and now we have minus x squared times the sum K equals 1 to infinity of BK X to the K so now notice that this guy is already equal to B of X which was our generating function but this guy is missing one term so notice it's missing the very very first term so we can go ahead and add that very first term in and then subtract it out so that's what we'll do so we'll take this guy right here so we'll add the first term in by changing that sum so that it starts at K equals 1 to infinity of BK X to the K but then we have to subtract that out as well and we'll do that by adding a negative X ok good and now notice that's all multiplied by 6x so now let's see if we bring this down what do we have we have X plus 6 x squared plus 6 x times the quantity negative X plus B of X great because now this is the right generating function and then minus x squared times B of X ok good but now notice we have X minus times negative X so that's going to give us negative 6 x squared so in fact this is going to cancel with what we get when we distribute that ok great so what we have in the end is we will have X X and then plus 6 x times BX minus x squared times B of X so that's what we end up with ok so I'll bring that to the top and then we'll keep going ok so on the previous board we left off at this point so we've got this functional equation for our generating function for our balancing numbers so now notice we can move all of the terms with b of x over to the left hand side of the equation so that will give us v of x minus 6x b of x plus x squared b of x equals x so that's all that's left on the right hand side of the equation that we can factor a B of X out of this so notice if we factor a B of X out of this we're going to have x squared minus 6x plus 1 great and now that's so that's going to be equal to X B of x times this polynomial which tells us that B of x equals x over x squared minus 6x plus 1 ok great so now I'll go ahead and move that to the top and then we're almost ready to get closed form for these numbers ok so we ended at this we have the generating function for the balancing numbers is given by x over x squared minus 6x plus 1 and now I'm going to do without showing all the details I'm going to notice that this thing factors and you can figure out how it factors by solving x squared minus 6x plus 1 equals 0 with the quadratic formula and this guy is going to factor in the following way it'll factor X minus 3 plus 2 root 2 times X minus 3 minus 2 root 2 great so now let's maybe write that in the following form so let's maybe say alpha equals 3 plus 2 root 2 and let's say beta equals 3 minus 2 root 2 and so we can write that in a more succinct form as x over X minus alpha times X minus beta now the next thing we want to do is decompose this with partial fraction decomposition so in other words we want to write this as a over X minus alpha plus B over X minus beta so now we'll do that by multiplying both sides of this equation by the denominator and notice if we multiply both sides of this equation by the denominator the left-hand side will give us X and then the right-hand side keeping in mind that this denominator is x minus alpha times X minus beta we will get a times X minus beta plus B times X minus alpha good but now notice we can combine like terms over here we get a plus B times X good and then minus a times beta plus B times alpha okay so now equating the coefficients of X on both sides of the equation and the constants on both sides of the equation we get the following so the coefficients of x on both sides of the equation will give us a plus B equals one and in the constants on both sides of the equation will give us a times beta plus B times alpha equals zero so now notice we have a system of equations with two equations and two unknowns so notice our two unknowns are a and B and these are our two equations so I'm going to go ahead and write this as B equals one minus a and now we can put that into this equation and so notice that's going to give us a times beta plus one minus a times alpha equals zero which is going to give us a times beta minus alpha plus alpha equals zero but now notice that beta minus alpha is a nice number so beta minus alpha is going to give us three minus three and we'll have negative four root two so this is negative four root two times a equals negative alpha which tells us that a equals alpha over four times the square root of two okay so now we know what a is I'm going to clean up the board and we can use that to calculate B okay so on a previous board we calculated that a was equal to alpha over 4 root 2 where alpha is this number and now we have V as one minus a so that is going to be equal to let's write this as 4 root 2 over 4 root 2 minus 2 alpha but alpha is equal to 3 plus 2 root 2 over 4 root 2 okay so let's see what we get when we do that we're going to have minus three in the numerator now we have 4 root 2 minus 2 root 2 so that's going to be plus 2 root 2 over 4 root 2 now we can pull a minus sign out of that and notice that that will be minus beta over 4 root 2 so this is what we have for B okay so we have our partial fraction decomposition for a and B good so I'll clean up the board and then we will move on from there okay so our partial fractions brought us here so we have B of X is equal to 1 over 4 times the square root of 2 times the quantity alpha over X minus alpha minus a beta over X minus beta so now I'm going to rearrange this a little bit I'm going to write this as 1 over 4 times the square root of 2 I'm going to take this minus sign and absorb it into the denominator to write this as beta over beta minus X good and then I'm going to pull a minus sign out of that to do something similar so this is minus alpha over alpha minus X and I'm doing this because I want to expand these as geometric series eventually so now the next thing I want to do is factor a beta out of this term in the denominator and an alpha out of the other term in the in the denominator and I can cancel those in the in the numerator so that's going to give me 1 over 4 root 2 here and then I'll have 1 over 1 minus x over beta so I've got that and then minus 1 over 1 minus X over alpha and now I can use a geometric series formula to rewrite this as 1 over 4 times the square root of 2 and then this is going to be equal to the sum K equals 0 to infinity of X to the K over beta to the K minus X to the K over alpha to the K so but notice that we don't need the K equals zero term here because that will cancel and now will give us exactly equal to one over four times the square root of 2 times the sum K equals 1 to infinity of we can write this as 1 over beta to the K minus 1 over alpha to the K times X to the K so next thing I want to do is I'll take this to the top and then we're almost ready to write down a closed formula ok so in the previous board we had the following so the generating function for the case balancing number was given by this 1 over 4 times the square root of 2 times the sum from k equals 1 to infinity of 1 over beta to the K minus 1 over alpha to the K times X to the K so now I want to combine those together so I'll give myself a common denominator which is beta K alpha K and that will give us the following so this is 1 over 4 root 2 times K equals 1 to infinity of so that's going to give me alpha to the K minus beta to the K over alpha beta to the K times X to the K so that's just finding a common denominator there but now let's notice that alpha times beta is actually a nice form here and that's because these are radical conjugates of each other so this is going to be 3 plus 2 root 2 times 3 minus 2 root 2 so that's going to give me 9 minus 2 root 2 squared which is 8 which is 1 so notice all of that cancels so that means alpha times beta is 1 which means alpha times beta to the K is also 1 so in other words we get this as 1 over 4 root 2 times the sum K equals 1 to infinity of alpha K minus beta to the K times X to the K but now extracting coefficients what we have is that be K in other words the case balancing number is given by 1 over 4 times the square root of 2 times alpha to the K but I'll rewrite what alpha is so this is 3 plus 2 root 2 to the K minus beta K so that's 3 minus 2 root 2 tuna k now we have a nice closed form for the case balancing number so I'm going to clean up the board and then we'll look at a summary of everything that we've seen ok so after all of that we have this nice summary so the case balancing number is described these nice three different ways so we have this two-step recursion so BK equals 6 BK minus 1 minus BK minus 2 where B 1 is 1 and B 2 is 6 we have this nice closed formula so BK is 1 over 4 times the square root of 2 times 3 plus 2 root 2 to the K minus 3 minus 2 root 2 to the K and also it's given by this generating function so the sum from k equals 1 to infinity of BK X to the K is x over the quantity x squared minus 6x plus 1 so we've done a lot in this video and I think this is a good place to stop

Channel: Michael Penn

Views: 45,556

Keywords: math, mathematics, number theory, abstract algebra, Randolph College, randolph, Michael Penn, generating functions, combinatorics, balancing numbers, triangular numbers, partial fractions, Bramagupta

Id: jMfZ9jRsHSI

Length: 40min 48sec (2448 seconds)

Published: Fri Mar 06 2020