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.
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
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.
@@franksaved3893 The claim eliminates the odds, but the remaining numbers are the evens, not the powers of two. But, as Berf says, the same argument can be used to eliminate any number containing an odd prime. It was probably just a slip, and "number containing an odd prime" was actually intended, instead of "odd".
The claim is also not worded correctly. It says gcd(m, a_n) != 1. But which n? Certainly not all n. His proof essentially* proves the following claim: "If m is a natural number which is not a power of 2, then *there exists* some n s.t gcd(m, a_n) != 1". *the only tweak would be that any m which is not a power of 2, has some prime factor p which is not 2 (he also implicitly uses the fact that p isn't 2 when writing (p-3)!).
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.
my approach would be a lot of work and after becoming pretty sure it would worked, i didnt finish, so i dont have a closed form. try this: trying a few iterations it becomes clear that you can always write Un = (An U0 + Bn) / (Cn U0 + Dn). so make that ansatz. plugging in the recursion, you get some coupled recursions for the (An Cn) and (Bn Dn). write them as a matrix equation, basically (An Cn)^T = M (A_{n-1} C_{n-1}). so you can find An and Cn by applying M^{n-1} to (A1 C1) = (4 1) You can do that by diagonalising M analogously for Bn Dn. of course that isnt a proof, since the ansatz is just guessed, but you can easily prove that it is correct, once you have the closed form
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.
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
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.
I guess you could make work of it very quickly. It is linear inhomogeneous recurrence. Much like with ODEs, you can guess inhomogeneous solution to be 1. The homogeneous one is also guessable (any you can find with arbitrary coefficient). You get a(n) = C * n! + 1
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, ...).
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).
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.
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
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. :)
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.
no because A(x) isnt a well defined function, we dont care about how it maps elements from its domain (sometimes inexistent) to its codomain. We only care about the coeficient of the x^n
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
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!*
Much quicker ! and simpler too...
Lol
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.
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
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. :)
Such a brilliant trick at the end!
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.
power of two*
its*
(clearly the upvotes indicate these corrections were not necessary to understand what you meant).
@@chaoticoli09 The fellow just likes rhyming in addition to mathematics
The claim says m>=3 and odd.
@@franksaved3893 The claim eliminates the odds, but the remaining numbers are the evens, not the powers of two. But, as Berf says, the same argument can be used to eliminate any number containing an odd prime. It was probably just a slip, and "number containing an odd prime" was actually intended, instead of "odd".
The claim is also not worded correctly. It says gcd(m, a_n) != 1. But which n? Certainly not all n. His proof essentially* proves the following claim: "If m is a natural number which is not a power of 2, then *there exists* some n s.t gcd(m, a_n) != 1".
*the only tweak would be that any m which is not a power of 2, has some prime factor p which is not 2 (he also implicitly uses the fact that p isn't 2 when writing (p-3)!).
left side of the board reads:
Find all meN such that
god(man) = 1
this couldn’t have been on purpose, could it
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.
my approach would be a lot of work and after becoming pretty sure it would worked, i didnt finish, so i dont have a closed form. try this:
trying a few iterations it becomes clear that you can always write
Un = (An U0 + Bn) / (Cn U0 + Dn).
so make that ansatz. plugging in the recursion, you get some coupled recursions for the (An Cn) and (Bn Dn).
write them as a matrix equation, basically
(An Cn)^T = M (A_{n-1} C_{n-1}).
so you can find An and Cn by applying M^{n-1} to (A1 C1) = (4 1)
You can do that by diagonalising M
analogously for Bn Dn.
of course that isnt a proof, since the ansatz is just guessed, but you can easily prove that it is correct, once you have the closed form
@@jakobunfried2669 THANX ALOT MAN !!!
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.
Yes, that's an example of a 'summing factor'. I mentioned that too, but you were prepared to do much more typing than I was! :D
17:05
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
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.
Like this video very much. Got to learn tons of new techniques
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 💯💯💯
Great content. Thanks!
I'm so happy because , i have a time to do these greats problems
10:54 🤔
x will change
Because 2/(1-x)=sum(2 x^n) for Abs[x]
@ 14:35 there is no fan on this human pc, you have to drop the jacket
I guess you could make work of it very quickly. It is linear inhomogeneous recurrence. Much like with ODEs, you can guess inhomogeneous solution to be 1. The homogeneous one is also guessable (any you can find with arbitrary coefficient). You get a(n) = C * n! + 1
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, ...).
solution is really good
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
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).
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.
In fact this is linear recusion but with non-constant coefficients
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
Bài toán về dãy số. Phải tìm hiểu quy luật của dãy số.
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 👍👍👍
What a fantastic Friday problem.
Thank you, professor!
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. :)
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.
no because A(x) isnt a well defined function, we dont care about how it maps elements from its domain (sometimes inexistent) to its codomain. We only care about the coeficient of the x^n
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.
You have seen a lot of Michael videos when you solve a problem in the exact same way of him.
Good evening matematics
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
Awareness++
Nice one
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!
Yeah , goog problem , i will to solve