some of my favorite tricks/tools.

[@goodplacetostop2973]

6:08 New effect 14:44 one = -1 15:12 Good Place To Stop

[@allanjmcpherson]

I really like the quick animation showing the somewhat tedious ancillary calculations! It provides those details for those who want to see them without getting bogged down in material that might seem trivial for others.

[@MrRyanroberson1]

6:06 - 6:15 for those who want to know specifically when this happened, as well as 9:33

[@papetoast]

I agree, its a nice addition to the video

[@andreben6224]

The added small animations as "footnotes" are just a perfect touch. The solution seems so much mor fluid.

[@perrydimes6915]

Great problem. Love generating functions Another way of thinking of is that (2m)^2 + 1 is a square is a very special case, since (2m)^2 is a square itself. The difference between consecutive squares are the odd numbers. The only two squares which differ by only 1 are therefore 1 and 0.

[@megauser8512]

Yep, that makes sense!

[@yoav613]

Generating function and number theory in one video,not bad..not bad at all

[@tomatrix7525]

Great idea with these short notes. Saves time and people can pause if it’s something they’re confused with.

[@demenion3521]

Of course, you get no solution for the two factors having opposite signs since they won't multiply to 1 in the first place

[@vokuheila]

Yea I got so confused at that part. Started to question reality.

[@megauser8512]

Exactly!

[@DitDede]

Yeah, he should have considered the both=-1 instead, which has no solution.

[@retired5548]

I haven't touched on this technique yet, but using generating functions to solve recursions looks like an interesting way to get closed forms for otherwise tricky recursions. It also answers (to me, at least) why one should use generating functions in the first place with a pretty neat example. Pretty cool!

[@MathFromAlphaToOmega]

Another nice thing about generating functions is that multiplication by n is essentially the same as differentiating the generating function. Also, once you have a closed form for the function, you can use that to estimate the size of the coefficients. For example, the generating function for the Fibonacci numbers happens to be x/(1-x-x^2), which I think is proved in an older video. That function is undefined when x=1/phi, the reciprocal of the golden ratio. So the sum of F_n/phi^n diverges, but the series converges if we increase phi by any amount. That suggests that F_n is roughly the same size as phi^n, and in fact, that's correct up to a factor of sqrt 5.

[@f5673-t1h]

It gets really interesting when you have a number-theoretic recursion over the integers, but then you use generating functions and suddenly you have a differential equation on your hands.

[@kodirovsshik]

That's lovely to see how the quality of content improves a lot over time, these quick animations are such a cool idea!

[@christophniessl9279]

08:50 to prove that (4^n-(-1)^n)/5 is an integer view the denumerator modulo 5 and note that 4 is congruent to -1 (mod 5), basically (-1)^n - (-1)^n == 0 (mod 5) which means that the denumerator must be divisible by 5. □

[@pacojacomemaura2129]

That's a nice and short proof! Please note you should have written "4 is congruent to -1 (mod 5)"

[@JM-us3fr]

I believe you mean the “numerator” not the “denumerator.” The word “denumerator” sounds too similar to “denominator” which is exactly what you do *not* want to refer to.

[@nathanisbored]

who has been doing the editing recently? it seems like it improved the flow of the videos

[@kevinmartin7760]

14:46 How is this (one being 1 and the other being -1) a "case"? 1 and -1 don't multiply to 1. If we have to consider that "case", then what about the "case" where one is 42 and the other is 13?

[@skylardeslypere9909]

Yep, I had the same thought. I'm guessing that it shouldn't have been a case. Only "both equal 1" and "both equal -1" which yield the same solution.

[@niuhaihui]

To solve the closed form of a(n) in terms of a(0) and n, we can construct a new sequence b(n), such that b(n)=a(n)+(-1)^n/5, and b(n) would actually become a geometric sequence with common ratio of 4.

[@MrTeekyman]

A somewhat easier way to get there is to notice the terms a_n of this sequence after the first term alternate between being 1 mod 4 (when a_n = 4a_{n-1} + 1) and 3 mod 4 (when a_n = 4a_{n-1} - 1). The numbers that are 3 mod 4 can't be perfect squares, so ignore those. If a number is a perfect square and 1 mod 4, it must be an odd square, of the form a_n = (2k+1)^2 = 4k^2 + 4k + 1 for some integer k. But this means that the previous term a_{n-1} = k^2 + k, which is always even for integer k. Since all the values of a_n are odd after the first term, this previous value can only be the first term. So the only possible perfect squares are the first two terms. It's easy to get one of these to be a perfect square, but if we could find a value where a_0 = k^2+k is a perfect square then we'd get the maximum possible of 2. Note that k^2+k is sandwiched between adjacent perfect squares, k^2

[@muskyoxes]

Maybe i should have seen stuff like this before, but it was just magic to me how the closed form for a(n) came out. I was like "why are you messing with sums? We aren't summing the series, we just need the terms" and the terms just instantly popped out.

[@danv8718]

Fantastic, as always! It would be awesome if you did a series on generating functions.

[@sakethram538]

""could you solve a question from JEE Advanced 2021 --- it has given one of the toughest math sections in JEE history"

[@aram5642]

I got stuck at the point where n was converted into n+1, bit it didn't happen to x^n, somewhere around 3:00.

[@replicaacliper]

danggg nice analysis

[@tahirimathscienceonlinetea4273]

This is my favorite problem that I was looking for .very nice

[@manucitomx]

I love generating functions. Thank you, professor!

[@captainsnake8515]

What a fun problem! I’m surprised that the trick of doing partial fractions on a generating function wasn’t familiar to me. Now that I’ve seen it used, it feels like a nearly universal technique that can be used in loads of problems, yet somehow it’s never crossed my mind.

[@dkravitz78]

Generating functions are always fun but you could have shown that a2,a3,... are 3,5 mod 8 with simple induction. a1 mod 8=4a+1=(0 or 4)+1=1 or 5 a2 mod 8=4*(1 or 5)-1=4-1=3 a3 mod 8=3*4+1=5 a4 mod 8=5*4-1=3 And the pattern clearly repeats 3,5,3,5,... Then simple finish as you did

[@gaufqwi]

The explanation was great but the conclusion was kind of an anticlimax.

[@karolakkolo123]

Agreed lol

[@Yoyimbo01]

As a complete beginner in modular arithmetic, why is a_n for n>=2 never a perfect square if it is never a perfect square mod 8?

[@ethansolly96]

All perfect squares in integers reduce mod 8 to one of the numbers in the table he made (the quadratic residues). Since we know a_n mod 8 isn't ever in that list, it can't be a perfect square.

[@jacemandt]

Being a square just means that it's a number times itself, so the idea of "squareness" doesn't depend on the modulus. So every perfect square is is a square modulo *anything*. Thus, if it's not a square mod 8 (or anything else), it's not a square at all. He chose mod 8 because (unlike me) he could see that it worked out nicely once n≥2.

[@Nikolas_Davis]

It's just as well that only terms for n < 2 can be perfect squares, otherwise we'd have to maximise an infinity of terms, and I don't even know what that means 😐

[@tonyhaddad1394]

If that the case then no maximized solution !!!

[@Nikolas_Davis]

@@tonyhaddad1394 But one could still ask if the percentage of perfect squares within the first N terms tends to some fixed value as N -> Infty. In general, such questions are notoriously hard to settle.

[@megauser8512]

@@Nikolas_Davis Yep, sadly!

[@OunegNebty]

Professor Penn I don't understand : you apply geometric series for (-1)^n*x^n and the results is 1/(1+x). But there is no indication that -1

[@karolakkolo123]

Generating functions are not meant to be treated as true functions and so it doesn't even matter if they converge or not. Remember, the variable in generating functions is only a dummy variable. We never actually evaluate a generating function. Generating functions are just neat tools that we can use to represent an infinite sequence of numbers in a compact way

[@stewartzayat7526]

The new animations are pretty sweet! I'd love if they were just a touch slower since I had a hard time reading through them without stopping the video.

[@atrumluminarium]

This was amazing

[@stevenmellemans7215]

Ok, a generating function, that’s fine, but does that function exist? How can we be sure there exists an x for which the generating function converges? I’d pull out a complete induction proof to be sure the solution makes sense.

[@MathFromAlphaToOmega]

That's a valid question, but often, the convergence of the generating function doesn't actually matter. The powers of x are really just a way to keep track of the sequence, and we don't need to plug anything in for x here. You could even have a generating function that almost never converges, like the one for the factorials. The series 1+x+2x^2+6x^3+24x^4+••• only converges when x=0, but you can still use that function to analyze properties of the sequence.

[@christophniessl9279]

the idea is called a formal power series and belongs to algebra (and algebraic geometry) rather than analysis/calculus en.wikipedia.org/wiki/Formal_power_series The set of formal power series in the variable X over any ring R is denoted R[[X]], so we are calculating in Z[[X]] in this video

[@christophniessl9279]

second way to work with this: A(x)is obviously convergent for x=0, and when one views it as Laurent series around z=0, the convergence radius is the distance from 0 to the next (non removable) pole which is r=0.25, as the poles of A(x) are z=-1 and z=0.25 (c.f. 6:30)

[@stevenmellemans7215]

Thanks for the information. I always use a Z-transform to solve a set of recursive equations but while doing so I always picture myself that a mathematician is calling me bad names because I never prove that these functions are Z-transformable. After the inverse Z-transform I always check that the result does solve the original equation by complete induction. I will look into the ring of formal power series and generating functions in more detail, it looks like an interesting technique. Thanks again.

[@niuhaihui]

It's pretty easy to see a2=3 mod 8, then a3, a4, a5, ... alternate between 5 mod 8 and 3 mod 8 due to the recursion. And the problem is essentially solved.

[@panPetr0ff]

How to solve the sum{n=0 to infinity} a(n) ...where a(0)=1, a(n) = a(n-1)*(3/2n - 1) ? I tried a way using generating functions, stucked on the term: x/2 * sum{n=0 --> inf} a(n)*3/(n+1)

[@xyzx1234]

Maybe I'm too tired because it's Friday night, but why does 4^n ≡ 0 (mod 8) imply that (4^n)/5 ≡ 0 (mod 8)? Isn't the latter a non-integer? Similarly, isn't -(-1)^n / 5 a non-integer? How can it be congruent to ±5?

[@p.abhijitsuhas26]

had the same question

[@boundary.alchemy]

Great question! To have been more rigorous, I would have done the following: since gcd(5,8) = 1, we know that division by 5 modulo 8 is well-defined because there exists 5^-1. Since 5*5 = 25 = 1 mod 8, 5^-1 = 5 itself. Thus we have [4^n - (-1)^n]/5 = [4^n - (-1)^n]*5^-1 = [4^n - (-1)^n]*5 = +5, -5 mod 8 for n>=2. Hope that helps!

[@xyzx1234]

@@boundary.alchemy Thank you! I didn't know that there is a sensible definition of division in modular arithmetic. This means that in this proof we switch from one definition of division to another, the validity of which (to me) is nontrivial, but I'm sure justified.

[@beautyofmath6821]

Wow, nice.

[@polarisator9892]

One could also decompose a_n into a homogenous and a partial part: a_n = a_p,n + a_h,n, where a_h,{n+1} = 4*a_h,n and a_p,{n+1} = 4*a_p,n +(-1)^n A solution for the partial part is a_p,n = A*(-1)^n. a_p,{n+1} = -A*(-1)^n = 4*a*(-1)^n +(-1)^n -A=4*A+1 A=-1/5 The homogenous part would be: a_h,n = B*x^n => x*B*x^n = 4*B*x^n x=4 Thus a_n = B*4^n - 1/5*(-1)^n a_0 = a = B-1/5 a+1/5 a_n = (a+1/5)*4^n-1/5*(-1)^n This approach can also be used for getting and explicit form for the Fibonacci sequenz: a_{n+2} - a_{n+1} -a_n = 0; b_n = a_{n+1} +p*a_n b_{n+1} +q*b_n = a_{n+2} + (p+q) *a_{n+1} + p*q*a_n = 0; p+q =-1; pq=-1; p^2+p+pq = p^2+p-1=0 p=1/phi; q=-phi b_n = A*(-q)^n -q*A*(-q)^n+q*a*(-q)^n = 0 a_{n+1} = -p*a_n+A*(-q)^n; a_n = B*(-p)^n +C*(-q)^n -p*B*(-p)^n-q*C*(-q)^n = -p*B*(-p)^n+(-p*C+A)*(-q)^n; A= (p-q)*C a_0 = 1; a_1=1: B+C = 1; -1/phi*B+phi*C =1 a_n = ((phi-1)*(-1/phi)^n+(1+1/phi)*phi^n)/(phi+1/phi)

[@mrminer071166]

Unsatisfactory. I was hoping to see different choices of a lead to different sprinklings of squares throughout the a's. Seeing the whole thing collapse to a0 & a1, and then to 0 and 1, left me feeling like this was a trivial problem. ;( Love the quick animations tho.

[@zygoloid]

a1=4a+1 a2=4a1-1=4(4a+1)-1=16a+3 ... so a2 is never a square because 3 is not a square mod 4. Note that a=0 gives a1=1, both squares, so a=0 maximizes the number of initial squares in the sequence.

[@barisdemir7896]

(-1)^1 = -1 there was a problem last of video. attention plz