Romanian Mathematical Olympiad Problem

[@nickgrivas2761]

the most QUALITY channel in the WHOLE universe

[@ruscul8711]

yup... but the audience is small 'cause only a few appreciates brilliancy and many for entertainment.

[@pcbenutzer6651]

true bro just true

[@vikaskalsariya9425]

yea

[@mtaur4113]

needs moar lightsaber fights, less maths j/k

[@MathLab4u]

We like the way he taught

[@tamarov]

I'm Romanian and I instantly recognised this problem as I had to solve it as part of a math contest a few months back. It was featured in the Romanian Mathematical Gazette in December last year and aimed at 9th graders. It was first proposed by Marcel Țena as part of the runoff after the National Mathematical Olympiad in 1981 (the test to determine the contestants for the IMO). As for my approach solving the problem, finding the closed form was the easiest part for me (I used a different method I was already familiar with, without using induction) but it took me a while to finish the solution via Fermat's Little Theorem. Also, I found the approach by generating functions very interesting and I will definetly try it in the future when dealing with more complicated series. Overall great video, I'm glad the international math community is interested in our olympiad problems.

[@codruta4396]

bunaa! pentru care clasa a fost propusa problema? n am gasit o :)

[@tamarov]

@@codruta4396 clasa a 9a

[@codruta4396]

@@tamarov mersii

[@blueghost3649]

Wow, mai există români care se uită la canalul ăsta

[@jacemandt]

Just generate a few values? a_0 = p a_1 = 2p-1 a_2 = 2(2p-1)-1 = 4p-3 a_3 = 2(4p-3)-1 = 8p-7 It's clear that the pattern is a_n = (2^n)p - (2^n-1), which is equivalent to what you got, and which you could prove by induction if you even feel the need for a proof at that point. The technique of the generating function is new to me, and seems very versatile and interesting, and is thus appreciated, but like other commenters said, maybe overkill for this particular sequence.

[@rogerlie4176]

Of course he could have solved this particular problem with more primitive methods, but by introducing generating functions he gives us a tool that is very useful for many type of problems.

[@malawigw]

yeah I would try with a similar approach as you

[@JB-ym4up]

he demonstrates a powerful technique on a easy problem so the problem isnt the focus of the lesson.

[@HarmonicEpsilonDelta]

Arg, I wasn't the only one to think that hahahaha good work dude

[@valeriobertoncello1809]

@@rogerlie4176 truh

[@iwonder2218]

Thanks for the videos, keep up the good work. Another way to solve this is subtract 1 from both side of recurrence to get (An+1)-1 = 2((An)-1). Let Bn = (An)-1 and get Bn = 2^n(B0). Substitute back in and get An = 2^n(A0 - 1) +1.

[@MichaelPennMath]

Wow, that is very elegant!

[@kwea123]

@@MichaelPennMath It's sort of the standard way to solve this kind of order 1 recurrence. What we call this is "finding the fixed point", by solving x for which x=2x-1 (replace An and An+1 by x), then you'll have (An-x)=2^n(A0-x) and all is done.

[@robertgerbicz]

@@MichaelPennMath It works for any u(n)=A*u(n-1)+B sequence, what would be C for that v(n)=u(n)+C is a geometric serie.

[@piwi2005]

Just seen your answer. I guess in Romania, they learn generating functions before characteristic equations :)

[@shmuelzehavi4940]

The same.

[@f5673-t1h]

Expanding a couple of terms quickly gives you the formula a_n = p*2^n - (2^n - 1). No need for generating functions, but it is a good idea to introduce them.

[@ionutradulazar8984]

The sequence b_n = a_n - 1 has a much nicer recurrence relation, namely b_(n+1) = 2b_n which can be solved easier, but it is nice to be able to "brute force" your way through a problem when needed and it was also great for learning purposes to see generating functions being used

[@alonamaloh]

a_n = (2^n)p - (2^n - 1) (trivial by induction), so make n = p-1 and then a_{p-1} = 2^{p-1}p - (2^{p-1} - 1), which is a multiple of p because of Fermat's little theorem.

[@fraserpye9667]

I love it how you always go to the most crazy solution, it helps me learn more complex methods of approaching problems, and exposes me to new ideas. Wilsons theorem makes this question a whole lot easier!

[@vlix123]

Here’s a generalisation: Let a[n] be a sequence of integers such that a[n+1]=ba[n]+c where b and c are integers. Prove that, for some m>0, |a[m]| is composite.

[@antoniopalacios8160]

Great video. By hand, for p=2 I get with a3=9 the first composite. Thank you.

[@sahilbaori9052]

He should have a t-shirt with "okay great" written on it. I'll buy it.

[@MichaelPennMath]

lol

[@vikaskalsariya9425]

ye

[@MichaelPennMath]

Maybe i'll release this shirt for an x-subscriber celebration. What should this x be? How fast can we get there?

[@sanjaysuresh8865]

@@MichaelPennMath 20k?

[@vikaskalsariya9425]

@@MichaelPennMathno at 25k it should atleast be a perfect square?

[@juanixzx]

Wow, you are improving your teaching skills, I got it just right away and no need of being studying pure maths. Thank you, teacher, Regards from Colombia.

[@mrphlip]

Before looking at the hints (from just the thumbnail): First, as special case, look at p=2: a_n = 2, 3, 5, 9, we have a composite. Now, the odd primes: consider the integers mod p. The function f(n) = 2n - 1 is invertible mod p (since 2 and p are coprime). Also, the integers mod p only has finitely many elements (there are p of them) so iterating f multiple times will eventually repeat. Say the first repetition is a_i = a_j (mod p), i < j. If i > 0, then we can write f(a_i-1) = f(a_j-1) (mod p), and then a_i-1 = a_j-1 (mod p) since f is invertible. But we said i,j was the first repetition, so this is a contradiction, and i=0. So a_j = a_0 = 0 (mod p). So a_j is a multiple of p. But the sequence of a_n is also strictly increasing, since f(n) > n for any n > 1, which includes a_0 and thus all the later a_n's, which means that a_j > p. a_j being larger than p and a multiple of p implies a_j is composite. I'm now watching the actual video with interest, as the hints imply a rather different proof (a constructive one)... I can see how with some effort and FLT you can probably find that j = p-1 (or some factor thereof)... but for a non-constructive proof you don't need to go that far.

[@yukihyde1]

sorry but it appears that f(n)=2n-1 and p must be coprime, not 2 and p, to make f(n) invertible modulo p.... can you explain that plz?

[@mrphlip]

@@yukihyde1 To invert it, we need to add 1 and divide by 2... The former is always possible, the latter is only possible if 2 and p are coprime.

[@yukihyde1]

@@mrphlip oh i see. i think your solution is brilliant. well, it seems the solution in this video is a little bit obvious so... keep up with the good job :)

[@ramk4004]

For the case p=2, since a_n = 2^n(2-1) + 1. We notice that 2^3 + 1 can be factorised into (2+1)(2^2 - 2 +1) = 3x3 = 9. Great video and nice, simple explanation. Thank you very much, Sir.

[@MichaelPennMath]

Thanks for sharing!

[@skylardeslypere9909]

Also 2^6 + 1 = 65 which is composite

[@sayanjitb]

@@skylardeslypere9909 there are many possible n values , 5,6,7... One can find in order to make a(n) composite. Isn't it?

[@dujas2]

When n is odd, 3 is always a factor. When n is congruent to 2 (mod 4), I think 2^n+1 is always composite as well for n>2. An example: 2^102+1=2^102+2^52+1-2^52=(2^51-2^26+1)(2^51+2^26+1)

[@piwi2005]

The equation can be rewritten as a(n+1)-1=2*(a(n)-1), with characteristic equation x=2. So we get a(n)-1=C *2^n. With a(0)=p , we get a(n)=1+(p-1)*2^n.

[@obnoxious2471]

If you write a(n) = 2(2(...2(p)-1)-1)...) -1, and "expand", you can "guess" that a(n) = p*2^n - (1+2+...+2^[n-1]) = p*2^n - 2^n +1, and then prove it with induction.

[@vikaskalsariya9425]

induction ewww

[@MichaelGrantPhD]

Indeed the generating function approach seemed like overkill

[@DaniErik]

Did the same. Obv the generating function approach is a good tool for cases when it’s hard to guess, but for this problem and under time pressure of a contest the guess and price method is faster and less error prone.

[@giuseppebassi7406]

Try this instead: create an auxiliary progression, namely Bn=An-1. So B(n+1)=A(n+1)-1=2(A(n)-1)=2Bn. B(0)=A(0)-1=p-1. So Bn is a geometric progression, since B(0)=p-1 and B(n+1)=2B(n). We get the closed form B(n)=2^n (p-1). So An=Bn+1=1+2^n (p-1). Then conclude in the same way.

[@helloitsme7553]

For p=2 you could say a_0=2, a_1=3 and then define b_n=a_{n+1}. (b_n) will start with 3 so we know it contains a composite number, so then b_k is composite for some k so a_{k+1} is composite for some k, QED. (I prefer this over actually finding the first composite number)

[@dalibormaksimovic6399]

Even stronger assertion holds. If we double a0, and add plus or minus one, we would get composite number at some point. For instance the sequence: 2, 3, 5, 11, 23, 47 is prime number sequence with that property, but since 93 and 94 are not primes, sequence stops at 47. The proof is very similar, if we multiply a0 by 2 and add 1, we must do the same for each other term(just look for some modulos, you will see it works), and vise versa, if we double first term, and subtract 1, for every term we must do the same. The rest of proof is the same. This question appeared in Serbian National Olympiad for 12th grade.

[@antoniopalacios8160]

Your method is very good at getting a general formula for a_n+1= d*a_n-1 (for d belonging to N). This is: a_n=((d-1)*p-1)/(d-1))*d^n + 1/(d-1)

[@Blabla0124]

Using generating functions is maybe a bit of an overkill ... If you substitute a(n) = b(n) + c and choosing c = 1 then you end up with b(n+1) = 2b(n) b(0) = p-1 which is trivial to solve.

[@othman31415]

Generally, to find the closed form of a sequence a_n such that, a_0=p and a_{n+1}=r.a_n+s we try to find a real number x for which the sequence b_n:=a_n+x is a geometric progression with common ratio equals to r. Here is another similar ( and a bit harder) problem: Let p be an odd prime number and and a_n a sequence such that: a_0=p-1 & a_{n+1}=2a_n+1 Proof that one can always find a positive integer n (n>0) such that a_n is not a prime number.

[@kwea123]

just solve x for which x=rx+s (replace an+1 and an with x) then an-x=r^n(a0-x) in 1 second. It is the standard way to solve order 1 recurrence.

[@wavyblade6810]

The closed form for the sequence was far easier to prove by induction. But maybe it was an "overkill" on purpose. 15:35 to prove it, shouldn't we show that a(n) is an increasing sequence? It's trivial, but it's just about some formal stuff. For p=2, for instance m=3 or m=5 works.

[@050138]

Very interesting question! Was able to solve it using Fermat's Little theorem.... More over, that 'i' for which it is composite is (p - 1), for all odd primes p.... Let's represent nth term as a[n] Since a[0] = p and a[n] = 2*a[n - 1] - 1 we have a[1] = 2*a[1] - 1 = 2p - 1 a[2] = 2*a[2] - 1 = 2*(2p - 1) - 1 = 4p - 3 So we can see that in the nth term, the coefficient of p will be 2 multiplied n times and the constant term will be negative sum of all the powers of 2 from 0 to (n - 1), or a[n] = 2^n*p - (2^(n - 1) + ...... + 2 + 1) or a[n] = 2^n*p - [2^n - 1] or a[n] = 2^n*(p - 1) + 1 or generally or a[i] = 2^i*(p - 1) + 1 Now, Fermat's Little theorem states that if 'p' is a prime and 'a' is a natural number relatively prime to p (gcd of (a, p) = 0), then a^(p - 1) = 1(mod p) So for every odd prime (all primes except 2), as 2 is relatively prime to p, we have 2^(p - 1) = 1(mod p) We also have (p - 1) = -1(mod p) obviously Multiplying the two congruences, 2^(p - 1)*(p - 1) = -1(mod p) which means 2^(p - 1)*(p - 1) + 1 is divisible by p But 2^(p - 1)*(p - 1) + 1 is nothing but a[p - 1] So we proved that for all odd primes p, a[p - 1] is divisible by p and hence is a composite number If p is 2, then we have a[0] = 2 and a[1] = 2*2 - 1 = 3 which is an odd prime, for which we already have proven that there will be an i such that a[i] is composite. Hence proved for all primes QED

[@050138]

@@angelmendez-rivera351 yeah true, didn't check his solution before posting.... Though it felt he used a very long drawn approach for identifying the closed form.... Kinda more rigorous I guess, though it was obvious.... And can be proved by induction!

[@jerrymouse3420]

chaman charlie,i did it in the exactly same way as you described..using fermat's little theorem..this pblm was easy.

[@n00bkillerleo]

Loved seeing a generating function for the first time, but couldn’t we have tried deducing the closed form using some iterations and then confirmed with something like induction?

[@websnarf]

Many generating functions can be solved that way. But its usually long winded and tedious to do all of that. SO generating functions are a way of encapsulating all of that into fewer steps.

[@shacharh5470]

If you will settle for a non-constructive proof, you don't need to use Fermat's little theorem. 1. closed form formula: a_n = 2^n(p-1) + 1 2. = -2^n + 1 mod p 3. for any p>2, 2 is generates the group Z_p, therefore for some n>0 2^n = 1 mod p 4. for that n, -2^n = -1 mod p 5. for that n -2^n + 1 = 0 mod p 6. That number is divisible by p but strictly larger then p so it's gotta be a composite

[@yeahyeah54]

i thought about this: in mod P a1=-1, then a_n = -2^n+1, since (Z_p,*) is ciclic then there is some n such that 2^n=1, hence a_n is divible by p

[@MichaelPennMath]

That is a very nice algebraic approach and I like it better than the approach I used. That being said, I think Fermat's little theorem is more likely to be in a math competitors tool-kit.

[@yeahyeah54]

@@MichaelPennMath i used cyclicity but i could use Fermat's little theorem

[@yeahyeah54]

sorry for my bad english, your work is really appreciated

[@ElchiKing]

except p=2 (in this case, we need to go to mod 3). A different, elementary argument is the following: let A_n=-2^n+1 mod p. Then there are at most p distinct values for A_n, so for some 0

[@tilek4417]

Love this channel so much

[@minime1235able]

Could I suggest using the cover up method for the partial fractions in some of these videos? I think it's a really quick and powerful tool for Olympiads.

[@AhmedBachir]

I found a more simple way for the first step Since we have a(n+1)=2a(n)-1 we get a(n+1)-1=2a(n)-2=2(a(n)-1) then the sequence (a(n)-1) is a geometric sequence hence a(n)-1=(a(0)-1)2^n which implies a(n)=(p-1)2^n +1

[@sanjaysuresh8865]

I think a faster way of achieving a closed form from a recurrent sequence is using a characteristic polynomial. No matter what the sequence is, it's very quick.

[@jasonroberts2010]

a0=2, a1=3, a2=5, a3=9 9 is composite for a0={2,3,5} the sequence reaches a composite number. all prime last digits from this point end in {3,7,9} a0=last digit a 3, a1=last digit a 5, therefore composite a0=last digit a 7, a1=last digit a 3, a2 therefore composite a0=last digit a 9, a1=last digit a 7, a3 therefore composite qed this works right?

[@sandorszabo2470]

Without generating function: a_(n+1) - 2 a_n = -1 is a difference equation. First solve the homogeneous equation. Find the solution in the form a_n:=q^n. Etc.

[@j9dz2sf]

First part faster: a₁=2a₀-1 ; a₂=2a₁-1=4a₀-3 ; a₃=2a₂-1=8a₀-7 ; the pattern seems to be an=2^n a₀-(2^n-1) which can be proved by induction. Can be rewritten : an=2^n(a₀-1)+1

[@elkincampos3804]

a_{n+2}-a_{n+1}= 2*a_{n+1}-1-(2*a_n-1)=2*a_{n+1}-2*_n. Therefore a_{n+2}-3*a_n+2*a_n=0 (equation in difference). We have x^2-3*x+2=0. Implies x=1,x=2 then a_n=a*1^n+b*2^n=a+b*2^n. But a_0=p and a_1=2*p-1. Therefore a_n= 1+(p-1)*2^n.

[@FaerieDragonZook]

How I would solve it. Note that a0 = 0 mod P. a1 = -1 mod P. If you apply the recursion formula with a1=-1, you get aN = -2^N +1 = -(2^N -1), which is always true mod P. Then you apply Fermat's little theorem to find that a(P-1) will be divisible by P, but strictly larger than P, so it is composite. For the case P=2, obviously you check that a3 =9 which is composite.

[@Reliquancy]

I just subscribed after this second one of yours I’ve seen... Wow, you’ve done like 200 videos in the last 9 months? cranking them out

[@chrissydude1]

Genuine question: Has it been proven that no generating formula for primes CAN exist or is it just well known that no generating formula has been found?

[@duncanhw]

The latter. There is actually a generating formula for primes (called theta-something?), but it's defined by primes so it's cheating-it's done in reverse. They've proven that it exists though, so they are possible.

[@joshuajodrian7364]

Great video as always! Your videos are always super easy to understand

[@loveforsberg530]

You said that if we could not prove the statement, we would get a generating sequence for primes, but in priniple it could be the case that we know that it fails for some (or even infinitely many) primes p, without knowing which primes.

[@HagenvonEitzen]

Actually, the whole problem is almost a one-liner: Given $m$, $a_{n+1}\bmod m$ depends only on $a_n\bmod m$, hence the sequence is *eventually periodic* modulo $m$. In fact if $m$ is odd, $2$ is invertible and the recursion function is bijective, meaning that the sequence is *immediately periodic*. Take $m=2a_0-1$, which is an odd number $>1$. Then the sequence contains infinitely many multiples of $m$. For $a_0>1$, the sequence is strictly increasing, hence these multiples of $m$ cannot all be $m$ itself.

[@drdeconstruct9341]

If this was in a competition I would (this is how I did it) work out some of the terms of a_n and then prove a closed form with induction. Its not too hard to see the pattern pretty quickly and I think its much more efficient than the more general method. I originally tried the problem before watching the video and thought I needed to show it was composite for all n, p=2 gives us a trivial counterexample when the closed form collapses to the form of a mersenne prime!

[@joshgoldman5107]

Much easier to find the closed-form formula with induction

[@chunchen3450]

Thanks Michael, your video frequency is amazing, keeps my brain busy😊

[@konraddapper7764]

Very nice solution My solution solution was to look at the entire series mod p resulting in b0=p mod p =0 bn+1=2bn-1 mod p This can be solved by guessing the explicit form. And proofing it via induction bn=-(2^(p-1)-1) mod p Afterwards the proofs are identical

[@MA-bm9jz]

You can look it up on art of problem solving,there most problems are archived really where,especially the romanian contests(as i am also from romania)

[@dalehall7138]

Nice treatment there. When I would treat partial fractions, on problems where the individual factors were linear, I'd recommend setting x equal to the roots of the individual factors. The result (if the original problem had no complex roots) is getting no systems of equations. But n separate equations (separate in terms of the coefficient being sought) for the coefficients of the decomposition.

[@fasihullisan3066]

you is my best teacher.

[@ВасилийТёркин-к8х]

2:40 - 13:06 using generating function to find closed form for a_n

[@TurboD89]

My aproach: Case p=2: look for the n. Case p!=2: Once you get a_n = 2^n(p-1)+1, deduce that for some n>0, 2^n = 1 mod p, since p prime, and thus a_n is a multiple of p.

[@arthurgames9610]

But why have you done all this? You could do: a0=p. a1=2p-1. a2=(2^2)p-2-1... an= (2^n)p-2^(n-1)...-1 ---> a(n+1)= 2^(n+1)p-2^n-...-1 (hypotesis induction). So, an= (2^n)p-((2^n)-1)/(2-1)= 1+(2^n)p-(2^n) = 1+(2^n)(p-1). I think this way is easiest

[@AnkhArcRod]

I thought, using the fact that (a_n+1 - 1) = 2(a_n-1), one can quickly derive the desired expression. But, I did like your approach for general instructional value!

[@djvalentedochp]

Your videos are AWESOME!!!!!

[@RiemannXiFunction]

Apostol's Introduction to Analytic Number Theory, exercise 5.14 is similar version of this problem.

[@sentipy8990]

Why do we assume that -1 < x < 1 when we convert "sum(x^n)" to "1 / (1 - x)"?

[@fernandoavalos5528]

I was asking the very same thing.

[@elyades2480]

That's because sum(x^n) from 0 to infinity is equal to (1 - x^(n+1))/(1-x) If -1 < x < 1 then x^(n+1) Can be discarded as it is arbitrarly small

[@liamhopson2913]

Simply its to do with convergence. If x was greater than 1 or less than -1, the sum would explode to infinity or behave nastily. If x is in that range then it converges nicely. Eg consider x=2 then sum is 1+2+4+8+... x=-1 then sum is 1-1+1-1... x=1/2 then the sum is 1+1/2+1/4+1/8+.... This converges to 2

[@MichaelPennMath]

I have to admit, in my mind x is a "formal variable" that is the generating function is only a combinatorial tool used to analyze the sequence.

[@websnarf]

Generating functions are a tool for manipulating coefficients, which is all he is using it for. He doesn't discuss the domain of x at all. x could be a complex number, a matrix, or perhaps the element of a very strange field. It is sufficient that there be *some* values of x for which the "=" is valid. Since x being a real number between -1 and 1, as you suggest, is such a valid domain, then it is perfectly sound for him to use the generating functions as he is.

[@nontth5355]

I think this solution is too complicated than it's needed to be.I mean just a_n+1=2(a_n)-1 (a_n+1)-1=2((a_n)-1) b_n = (a_n)-1 b_n+1=2(b_n) b_n=(2^n)b_0 Change b_n to a_n Almost done...no need for generate function.

[@__zenon]

As a general rule, just because two infinite sums converge to the same number doesn't mean that the n-th member of both sums is equal for all natural n's. I feel like it hasn't been adequately proven that that is the case here. Am I missing something?

[@HGCFGHFHJ]

THERE IS A ANOTHER APPROACH IF WE OBSERVE THE RECURRENCE T1=2P-1 T2=2^2P-3 T3=2^3P-7 NOW THERE ARE TWO PATTERNS ONE WITH POWER OF 2 AND ANOTHER IS 1,3,7,15 OBSERVING THAT THESE ARE 2^M-1 FINAL BECOMES Tm=2^M*P -(2^M-1) WE PATTERN IN 1357 IF NOT OBSERVED U CAN FORM RECUREENCE FOR IT AS An=An-1 + 2^n-1 then it is easily solvable

[@JacobGoodman]

Using a generating function was some serious overkill, but it was neat to see either way.

[@MichaelPennMath]

You are totally right!

[@Mathelite-ii4hd]

you could easily solve for an like this:let bn=an-1 then an=bn+1 pluging in we get bn+1=2bn so if we write the equation for this we'll get x^2-2x=0 so x1=0 and x2=2 so bn=c1(x1)^n +c2(x2)^n that is the same as bn=c2(2^n).now we know that a0=p so b0=p-1 so c2=p-1 .so bn=(p-1)2^n so an=(p-1)2^n +1

[@yanmich]

I would like to suggest the following problem: Consider the sequence a_n with a_1 = 1 and 3a_{n+1} = (a_{n})^4 + 1. Does it converge and to which limit? What if a_1 =2?

[@aerogomu]

Great channel. next time plz try Korean math olympiad problems

[@madcapprof]

A very convoluted way to find the closed form. a0=p a1=2*a0-1=2^1*p-1 a2=2*a1-1=4*p-3=2^2*p-2-1 It appears that a1=2^1*p-(2^1-1) a2=2^2*p-(2^2-1) Let us assume an=2^n*p-(2^n-1) a(n+1)=2*an-1 =2^(n+1)*p-2^(n+1)+2-1 =2^(n+1)*p-2^(n+1)+1 =2^(n+1)*p-(2^(n+1)-1)

[@demenion3521]

I know you like your generating functions, but here's the derivation of the closed form using characteristic functions: Since the recurrence relation is linear and inhomogeneous, we can split the solution in a homogeneous (b_n) and a particular part (c_n) with b_(n+1)=2b_n. This, we can easily solve by the fundamental ansatz b_n=C*r^n (where C is some constant). Plugging this ansatz in the homogeneous equation, we get r=2. Then for the particular solution, we can make the guess c_n=A for some constant A. Plugging this in the original equation yields A=1. The full solution is then given by the sum of the homogeneous and particular solution, so a_n=b_n+c_n=C*2^n+1. We can determine C=p-1 by using the initial value a_0=p. I don't mean to offend you, but in my opinion, this is a simpler way of deriving closed form solutions of "easy" linear recurrence relations.

[@iuliusconstantcornelio2018]

How hard do you want the Maths problems to be ? Romania: YEEEEEEESSSSSS !

[@mat1305h]

I mean the main part of the video can be skipped if you notice that a_{n+1} - 1 = 2(a_{n} - 1). Setting b_{n} = a_{n} - 1, it's very easy to find the closed form of a_{n}. In general if you have a_{n+1} = m a_{n} + p, with m!=1, you should solve for a = m a + p, and subtract a from both sides to get an easy closed form using the above technique.

[@shmuelzehavi4940]

@@mat1305h That's right. I intended to give the same solution.

[@AnkhArcRod]

In my humble opinion, this was a fairly tractable problem as far as Olympiads go as it required almost direct plug in of Farmat's little theorem.

[@dmitripogosian5084]

Funny how you explain trivial solution of linear equations on C and B coefficients in minute detail, but then start throwing mod function without any pause.

[@eliardosoarescoelho4333]

Nota 10000000.... parabéns, mais alguém do Brasil?👏👏👏👏👏👏👏👏

[@sofly666]

Acho que não velho

[@eliardosoarescoelho4333]

@@sofly666 kkkk🤦‍♂️ nós somos os únicos kkkkkkk

[@sofly666]

@@eliardosoarescoelho4333 kkkkkkkkkkkkk

[@shacharh5470]

using a generating function as you did was overkill. you can easily prove the closed form formula with induction.

[@techada347]

Kindly make a video on “Lifting The Exponent Lemma “

[@wavyblade6810]

6:19 to apply this formula we need an assumption that |x|

[@wavyblade6810]

same question at 11:41

[@wasitahmid749]

Do you make videos on combinatiorics

[@ghengheadaniel7007]

For p = 2 any composite number n will work.

[@gurusamy2911]

Are you using the hagaroma chalk? Because it sounds good

[@MichaelPennMath]

Always! Hagoromo would maybe be the only sponsorship I would accept if anyone out there is listening...

[@gurusamy2911]

Ha ha

[@Reliquancy]

Michael Penn It sucks it’s made up of ground up baby otter teeth though...

[@dabeev3006]

Lost me a bit with the mod relationships, which I'm not very familiar with. It seems odd to go through every step of partial fractions which are simple algebra, but not expand the modular math, which is a cornerstone of the whole proof, in more detail. Also, I appreciate his work here, but 4 to 5 ads for a 16 minute video is annoying, especially when they interrupt the middle of various sections of his video.

[@OfficialMGMusic]

I didn't know about generating functions of series, but it seems to be exactly the same thing as the z-Transform in digital signal processing, am I right?

[@HagenvonEitzen]

Really, generating functions instead of simply observing a_{n+1} -1 = 2 * (a_n-1) ?

[@Kurtlane]

Wow! Question: Can anyone recommend a good thorough book on generating functions. Covering algebra, calculus, linear algebra -- the whole enchilada. Thanks.

[@Bob-hc8iz]

The use of a generating function seems perilous as the chance of making a computation error under pressure seems huge. It is much clearer to consider the sequence mod p from the start as the solution is clear. If I were the problem grader I would deduct points for the use of a generating function as inelegant. I think it’s important in these problems to stress finding the simplest and clearest solution.

[@AlexandreRibeiroXRV7]

Why does "inelegance" matters when you solve a problem? If you have the tool and know how to use it correctly and it gets the job done, it shouldn't matter at all.

[@Bob-hc8iz]

@@AlexandreRibeiroXRV7 I'm just being a jerk. Sorry!

[@benjaminbrady2385]

I always found this weird: having n greater than one clearly makes the sums in the proof diverge and yet when all is said and done the conclusion is true (that being said I'm sure you could have just dragged around some dummy variable as an upper bound and probably made it work regardless but I've seen these proofs work in places where there doesn't seem to be any way to avoid going through some divergent strangeness)

[@matteopriotto5131]

Yeah I thought about that too. A(x) should converge for approximately -0.5

[@xaxuser5033]

why did u use a hard method while u can use ur observation to see a pattern write down a few terms and u can easily show using induction that an=(2^n)×p-((2^n)-1) and with this form it is much clearer that p divides an if n=p-1

[@adrianmisak07]

when we use generating functions to determine the closed form for an, we don’t have to worry about the convergence of sequences?

[@Quantris]

No generally not, x here is a dummy variable and you're basically assuming that you take domain of x small enough to stay in the convergent regime. That said I could imagine there's a way to get into trouble with this point in some complicated case (like if you somehow ended up with infinitely many denominators like "1-kx"). So it's not bad to point out that at each step here there is a well-defined region of convergence that we're staying in by assumption.

[@xaxuser5033]

how about generating fonctions of sequences like an+1=1+n/an ?

[@drd105]

Man, it's a 2nd problem I see you complicate to an absurd level. Here's something I have without writing a single thing on a piece of paper (typing this is the 1st time I am writing anything on it). a_n = 2^n p - 2^n +1 = -2^n +1 (mod p). Since p is a prime, 2^(p-1) = 1 (mod p). QED.

[@Mathelite-ii4hd]

and one question,when you wrote those geometric series ,you asuumed that |x|

[@Mathelite-ii4hd]

or else it is better to say that |2x|

[@derickalsept]

So my mathing is very limited (it's been more than a decade since I was in school), but isn't one example sufficient to prove the result? If you take p=2, then a_m=5 (maybe 4, I did the counting in my head) is 95, which is not prime.

[@JasonOvalles]

If the problem was saying to show that the sequence sometimes produces a composite number, then 1 example would suffice. But the problem is asking to show that the sequence will ALWAYS produce a composite number. Since we can't show all possible examples (there are infinite prime numbers we'd have to check), then we have to do a general proof.

[@lorianamesia331]

Was it the national or city Olympiad

[@mathematicalmonk1427]

Would you post theory lectures on olympiad mathematics

[@MichaelPennMath]

I am coaching my college's Putnam team in the Fall and will be making such videos over the Summer for this purpose.

[@lucagirelli5223]

@@MichaelPennMath Awesome! Cant wait for the videos

[@mathematicalmonk1427]

@@MichaelPennMath thank you very much

[@Balequalm]

@@MichaelPennMath That'll be delicous!

[@gurusamy2911]

@michael penn please post olympiad geometry theory lectures also

[@alexcheng9290]

Can you proof that any odd number greater or equal two 107 can be written as the sum of two coprime composite number? French math competition

[@zzz942]

Let N be an odd number, p is the least prime factor of N, q is the least prime factor of N after p. Here is a simple lemma: p+q is coprime with N. Pf: suppose it's not. Then some prime r>p,q divides p+q. p+q is even, which means that p+q=2*r*k for some k>=1. It follows that p+q>=2r. However at the same time p+q=1) is either coprime with N or p divides p+q-2i. p+q-2i is not a prime (it is even). N-(p+q-2i) is coprime with N. It is easy to see that no four consecutive N-(p+q-2i) are primes. So it implies that there are at most three terms between N-(p+q) and N-(p+q-2p). So p+q-(p+q-2p)=2p. So p==6 (p'=q'=3), which implies that p'q'>=9. So N>=5*3*9=15*9. So the proof ends because N=15*9=135 is the next odd multiple of 15 after 105. And starting with 107 gives you desired result.

[@alexcheng9290]

Thank you

[@copperfield42]

yeah, I could solve this one, I got a little stuck in the last part, but the hint of Fermat theorem was the last piece I needed for it :)

[@maxjackson6616]

could it be from the romanian master of mathematics competition?

[@helu7777]

p = 5 ?

[@suhailawm]

sir. how to prove let p is prime such that p>3 , for all p²-1 is multiple of 24

[@suhailawm]

its satisfy. but how to prove formaly

[@stephenbeck7222]

All primes bigger than 3 are equivalent to either 1 mod 6 or 5 mod 6, i.e. can be written as 6k+1 or 6k+5. Square both of those and subtract one and you get 36k^2+12k or 36k^2+60k+24, both of which can be shown quickly to be multiples of 24 (for the first one, consider cases of k even or k odd). Thus, n^2-1 is a multiple of 24 for any n that is equivalent to 1 or 5 mod 6 whether n is prime or not.

[@light_shaiful]

7:27 same. all those memories now behind ;(

[@Maniclout]

Hey like your channel, keep it up

[@chetankeshri804]

Perhaps the only question I could do all by myself

[@kryniu2181]

Go with polish olympiad. Im going to try my best to win this.

[@ekanshmallik7963]

You could have just used difference equation to get a form for a_n

[@MichaelPennMath]

I make no claims that my method of getting the closed form is the easiest -- I just default to generating functions because I think it is the most fun!

[@ekanshmallik7963]

Michael Penn ya no doubt they are fun. Keep on doing the good work brother.

[@padraiggluck2980]

When a_0 = 3, a_1 = 5, a_2 = 9

[@VibratorDefibrilator]

"So, let's go and look at the statement: So ,we wanna define the sequence a(n), where n goes... a(m) is not prime". Easy. That's a good place to stop... the video and to solve it... in your mind. Seriously, you should try to solve such problem with eyes closed, it improves inner vision.

[@malawigw]

I sometimes also miss my ex ...