Non-linear recursions are trickier (with a new technique!) 

Thanks for showing the exponential generating function method. However, I did it like this : *a(n+1) = (n+1).a(n) - n* => *a(n+1) - 1 = (n + 1)(a(n) - 1)* If we let *b(n) = a(n) - 1* , then *b(n+1) = (n + 1).b(n)* => *b(n) = n!.b(0)* Since *b(0) = 2* , we can deduce, *a(n) = 1 + 2n!*

You can rewrite the original recursion and avoid the generating function. a[n+1] = (n+1) a[n] - n = (n+1) a[n] - (n+1) + 1 = (n+1) (a[n] -1) + 1. Defining b[n] = a[n] - 1, we have the new recursion b[n+1] = (n+1) b[n], which has the obvious solution b[n] = b[0] n!, so a[n] = (a[0] - 1) n! + 1.

The fundamental theorem of arithmetic vaporized his hoodie.

14:35 Jacket comes off, math is getting serious. Either that or it's so straightforward that no more sleeve erasing will need to happen. :)

17:05

I have got following Cauchy problem for linear first order differential equation when i was calculating this generating function A'(x)=xA'(x)+A(x)-xe^{x} A(0) = 3 (1-x)A'(x) - A(x)=-xe^{x} A(0) = 3 This is linear first order differential equation and can be solved using integrating factor or variation of parameter Because it is Cauchy problem we have to calculate constant at the end

Such a brilliant trick at the end!

In the previous comments, Anindya Biswas and burpleson (and maybe others) gave the simplest algebraic derivation of the solution, but there's another common algebraic trick that also works here and is worth knowing. The trick is to consider how a recursion responds to factorials. Those 1 a(n+1) and (n+1) a(n) terms are screaming to apply the factorial trick. How that works here is noting that if you divide both sides by (n+1)!, those terms become a(n+1)/(n+1)! and a(n)/n!. Define b(n), for n>= 0, by b(n) = a(n)/n! (so a(n) = n! b(n)). Then a(n+1) = (n+1) a(n) - n, so (n+1)! b(n+1) = (n+1) n! b(n) - n, so (n+1)! b(n+1) = (n+1)! b(n) - n. so b(n+1) = b(n) - n / (n+1)!. Since that's like b(n+1) = b(n) - u(n), where u(n) = n/(n+1)!, have b(n) = b(0) - SUM{ k=0 to k=(n-1) of u(k) }. [Obvious from b(1) = b(0) - u(0), b(2) = b(1) - u(1) = b(0) - u(0) - u(1), b(3) = b(2) - u(2) = b(0) - u(0) - u(1) - u(2), etc.] Thus, for n>=1, have: b(n) = b(0) - SUM{ k=0 to k=(n-1) of k/(k+1)! } = b(0) - SUM{ k=0 to k=(n-1) of [ (k+1) - 1 ] /(k+1)! } = b(0) - SUM{ k=0 to k=(n-1) of [ (k+1)/(k+1)! - 1/(k+1)! ] } = b(0) - SUM{ k=0 to k=(n-1) of [ 1/k! - 1/(k+1)! ] } = b(0) - [ ( 1/0! - 1/1! ) + ( 1/1! - 1/2! ) + ( 1/2! - 1/3! ) + ... + ( 1/(n-1)! - 1/n! ) ] = b(0) - [ 1 - 1/n! ] = (b(0)-1) + 1/n!. Then use b(0) = a(0)/0! = 3/1 = 3 to get the final explicit form of a(n): a(n) = n! b(n) = n! [ (b(0)-1) + 1/n! ] = (b(0)-1) n! + 1 = (3- 1) n! + 1 = 2 n! + 1. I think for general linear recursions, the generating function technique is best, because you can often get it into a differential equation (or sometimes, like here, even a simple equation), and the techniques for handling differential equations are usually easier to see and compute than what would be the corresponding algebraic "trick" that would give the same result. But recursions also have many effective algebraic tricks worth knowing.

Great content. Thanks!

A summing factor also works well for this problem. Multiply the recursion by 1/product[(n+1) n (n-1) ... 1] = 1/(n+1)! and then sum both sides, giving a telescoping series.

You could also try solving this with ordinary generating functions, but then you'll get a differential equation whose solution is a divergent integral. Still, with some clever calculations, it should be possible to determine a_n that way.

That was really nice video 💯💯💯

Cool video, when i saw the title (non-linear recursion) i thought it would help with my homework, it goes like this: Un is a sequence defined by it's first term U(0)>1 and U(n+1)=(4Un+2)/(Un+5) Find Un in terms of n.

U can just play with trying to index shift and add one and stuff like that and you will find it. I could see the value in the method but its fqster to do the otger way

Dividing the both sides of the recurrence by (n+1) ! gives a(n+1) / (n+1)! = a(n) / n ! - n / (n+1) !, and we can rewire that as : [ a(n+1) -1 ] / (n+1)! =[ a(n) -1 ] / n ! = ・・・ = a(0)/0! - 1/0! = 2, yieding a (n) = 2 n ! + 1 (n=0, 1, ...).

I'm so happy because , i have a time to do these greats problems

The statement of the last claim is not sufficient. The claim should be for all m which are not a power of two. But the proof remains the same since if m is no power of two, its prime factorisation has at least one odd prime.

@ 14:35 there is no fan on this human pc, you have to drop the jacket

Seems like the audio is slightly desynchronized from the video? Maybe that's just my connection

13:41 😂😂 i really felt it so hard even though it's always obvious but to prove it is a pain in ass

left side of the board reads: Find all meN such that god(man) = 1 this couldn’t have been on purpose, could it

Like this video very much. Got to learn tons of new techniques

I solved it like this. I solve a_n for any a_0 by looking at the expanded (nonsimplified) formula for a_n. With that, I found that a_n = n! * a_0 + sum {k=1 to n} (n! (k-1)/k!) I also note that for a_0=1, a_n is always 1, so we get 1=n! + sum {k=1 to n} (n! (k-1)/k!) 1-n! = sum {k=1 to n} (n! (k-1)/k!) And substitute it to the original equation, so I get a_n = n! * a_0 + 1-n! a_n = n! * (a_0-1) +1 For a_0=3, we get a_n = 2*n! + 1

Before watching the video, since he challenged us to give it a go... a[n+1] = (n+1)a[n] - n = (n+1)(a[n] - 1) + 1 Substitute b[n] = a[n] - 1 b[n+1] = (n+1)b[n] = n!b[0] = 2n! So a[n] = 2n! + 1 Clearly, all of a[n] is odd, so if m is a power of 2 then it will be coprime to all of them. On the other hand, say m is not a power of 2, then it has some odd prime factor, call it p. It is a standard result that: (p-1)! = -1 (mod p) (p-3)!(p-2)(p-1) = -1 (mod p) (p-3)!(-2)(-1) = -1 (mod p) 2(p-3)! = -1 (mod p) 2(p-3)! + 1 = 0 (mod p) a[p-3] = 0 (mod p) so a[p-3] is not coprime with m. So only powers of 2 satisfy the condition.

Nice solution. For the last part, you probably don't mean to require that m be odd. You just need m to have an odd divisor (and therefore an odd prime divisor). Otherwise you haven't ruled out values like m=6. Also, your claim should be that *there exists* an n such that gcd(m, a_n) > 1. I don't think the claim holds for all n (and you certainly didn't prove that).

Bài toán về dãy số. Phải tìm hiểu quy luật của dãy số.

In fact this is linear recusion but with non-constant coefficients

The problem was in general easy. The only difficult and non-standard olympiad part was the trick at the end where you isolated the factors p-1 and p-2 to show that p-3 does the job. Note: We could have found the formula of a_n by writing x_(n+1) = (n+1)x_n (*), where x_n = a_n - 1. From (*) we easily see that x_n = n!x_0 and that's all. :)

10:54 🤔 x will change Because 2/(1-x)=sum(2 x^n) for Abs[x]

I love this problem ,very good technic to use the Wilson theorem in the last part that's tricker thing thanks Micheal for a good solution 👍👍👍

nice trick. . then i realised that a_n = 2n! + 1 formula can be obtained by writing out the first few terms of a_n and observing a pattern.

Um the claim should be not a power of 2, since if it is some number like 6, it is even but still has a odd prime factor. The grudge here is since the question asks for all m, and if you're seeing this, how do you know there aren't any other numbers that gcd(m,an)=1? So we have to partition the whole set of integers into two parts, prove the non tower of two part, show the tower of two part, and finish. Enjoyed the last trick btw

Nice one

What a fantastic Friday problem. Thank you, professor!

Awareness++

You have seen a lot of Michael videos when you solve a problem in the exact same way of him.

Good evening matematics

Shouldn't you prove existence of A(x) beforehand ? It is not obvious. If a(n) = n!*n^n the séries only exists at x=0. Obviously you can prove that the a(n) sequence found with your method verify the initial recurrent relation. But still, to be perfectly clean you should do it ;) best.

Not sufficient.... Even number are not all power of 2 The statement should be m greater than 3 with an odd prime... (not a power of 2) The proof remains the same tough

Yeah , goog problem , i will to solve

14:06 I think you made a mistake. It should be m>3 and *not a power of two*. Pin this so other people can see it!