/sci/ - Science & Math » Thread #12211652

27KiB, 1210x221, 1597253783948.png

View Same Google iqdb SauceNAO

How do you do this?

Anonymous Fri 09 Oct 15:04:22 2020 No.12211652 View Reply Original Report

Quoted By: >>12211675 >>12211689 >>12211906 >>12212292 >>12212690 >>12214947

How would you begin to prove this? Do you need to use binomial theorem?

Anonymous

Anonymous Fri 09 Oct 2020 15:07:12 No.12211657 Report

Quoted By: >>12211689

>Hint: Think about binomial coefficients
>Do you need to use binomial theorem?
Gee, I dunno, bud

Anonymous

Anonymous Fri 09 Oct 2020 15:12:18 No.12211675 Report

Quoted By: >>12211689

>>12211652
Maybe I'm just retarded but you could easily show, by contradiction, that the product of $(a+1)...(a+n)$ has a multiple of $1,2,...,n$ present.

Anonymous

View Same Google iqdb SauceNAO 67a86f04a706bf46f6d60b0fa89e566e.jpg, 28KiB, 410x461

Anonymous Fri 09 Oct 2020 15:17:38 No.12211689 Report

Quoted By: >>12211697 >>12211909

>>12211657
Retard.
>>12211652
No dude, you're overcomplicating it.
>>12211675
Overcomplicating it.

Solution
${a+n \choose n} = \frac{(a+1)(a+2) \ldots (a+n)}{n!} \in \mathbb{N}$

Anonymous

Anonymous Fri 09 Oct 2020 15:20:40 No.12211697 Report

Quoted By: >>12211703 >>12211729

>>12211689
okay maybe i'm just dumb, but why are we allowed to use the n choose k formula?

Anonymous

Anonymous Fri 09 Oct 2020 15:23:20 No.12211703 Report

Quoted By: >>12211713

>>12211697
Because it's true? The point is that n choose k is defined as the number of subsets of n of size k which obviously is an integer. The formula is easily proven. Thus the formula must be an integer too. Thus the numerator is divisible by the denominator.

Anonymous

Anonymous Fri 09 Oct 2020 15:26:06 No.12211713 Report

Quoted By: >>12211715

>>12211703
Fuck im being boosted. I could have said that if a = 1, then we have (n+1)!, which has to be a multiple of n!, fuck this was so free.

Anonymous

Anonymous Fri 09 Oct 2020 15:27:16 No.12211715 Report

Quoted By: >>12211730

>>12211713
This only works if a=1. What about in general?

Anonymous

Anonymous Fri 09 Oct 2020 15:31:24 No.12211729 Report

Quoted By:

>>12211697

because it has the combinatorial interpretation "n_C_k = the amount of |k| subsets of [n]". That number can only be an integer because it counts a number of sets.

If you prove it the way anon suggested, thne your proof depends on the combinatorial counting argument that proves this fact.

Anonymous

Anonymous Fri 09 Oct 2020 15:31:27 No.12211730 Report

Quoted By:

>>12211715
Hmm, if i do a=2, then we have \frac{(n+2)!}{2!}, and if a=3, then \frac{(n+3)!{3!} so then its \frac{(n+a)!{a!}. Is that where the formula comes in?

Anonymous

Anonymous Fri 09 Oct 2020 16:34:20 No.12211906 Report

Quoted By:

>>12211652
the integer is made up of n consecutive numbers, multiples of x appear once in every x consecutive numbers. for that integer to be a multiple of n!, it has to be a multiple of all factors in n!, due to the integer being made up of n consecutive numbers, it is a multiple of all of the factors so it is a multiple of n!

Anonymous

Anonymous Fri 09 Oct 2020 16:35:38 No.12211909 Report

Quoted By: >>12212204 >>12212292

>>12211689
>Overcomplicating it.
Except it's not over complicating it. Your solution uses more machinery.

Anonymous

Anonymous Fri 09 Oct 2020 18:12:38 No.12212204 Report

Quoted By: >>12212229

>>12211909
Dude your solution doesnt even work.
Just because every number 1 through n divides it, that doesnt imply n! divides it, since in general lcm(1,...n) is smaller than n!

Anonymous

View Same Google iqdb SauceNAO Screen Shot 2020-03-07 at 15.07.19.png, 29KiB, 238x259

Anonymous Fri 09 Oct 2020 18:23:47 No.12212229 Report

Quoted By:

>>12212204
>since in general lcm(1,...n) is smaller than n!

Anonymous

Anonymous Fri 09 Oct 2020 18:35:18 No.12212282 Report

Quoted By: >>12212472

Hint: (a + 1)(a + 2) = (a + 1)^2 + (a + 1)

Anonymous

Anonymous Fri 09 Oct 2020 18:38:54 No.12212292 Report

Quoted By: >>12212472 >>12212690

>>12211652
Notice that
$\frac{\prod_{k = 1}^n (a + k)}{n!} = \binom{a + n}{n}$
>>12211909
Not even. Binomial coefficients use minimal machinery (you can construct facts about them with elementary ideas) and provide a simple combinatorial proof. Divisibility proofs using binomial coefficients aren't easy to see but they're always good.

The easy-but-misses-the-simplicity way is to use induction and residue classes of integers to note that any set of k consecutive integers must be divisible by k. Subtract the largest multiple of k away from the set of integers. Then you have k distinct integers which have difference at most k - 1 among them, meaning they are all distinct (mod k). Then by pigeonhole, at least one must be 0 (mod k) -> divisible by k.

Anonymous

Anonymous Fri 09 Oct 2020 19:58:39 No.12212472 Report

Quoted By: >>12212516

>>12212282
How does that help?
>>12212292
>. Divisibility proofs using binomial coefficients aren't easy to see but they're always good.
Can you show me the proof?
>any set of k consecutive integers must be divisible by k.
You mean their product?
How does that help?

Anonymous

Anonymous Fri 09 Oct 2020 20:12:23 No.12212516 Report

Quoted By: >>12212553 >>12212599

>>12212472
>show me proof
The proof is above. The a + n choose n is a positive integer, so it holds. The hard part is seeing it
>their product
Yes, their product.
I just gave you the proof. Among k consecutive integers, you can put them in the residue class of k.
Suppose I subtract the largest multiple of k that is less than (a + 1) from that number. Then the difference is j, where 0 <= j < k. If j = 0, then k divides (a + w). Otherwise, if I subtract that number from (a + 2), the difference is j + 1. I continue in this way until there is some (a + m), where m <=n, for which the difference is j + (m - 1) = k. Then a larger multiple of k is less than (a + m), and so (a + m) is divisible by k. I can always do this because I have k consecutive integers, so there are k possible remainders when I subtract the multiple of k, and k unique remainders. Since every integer (a + i) is consecutive, their remainders are consecutive and this unique. Thus we have k unique possibilities and k unique remainders, and so there is exactly one integer among them that has remainder 0 and is divisible by k

Anonymous

Anonymous Fri 09 Oct 2020 20:22:11 No.12212553 Report

Quoted By: >>12212599

>>12212516
>Then the difference is j, where 0 <= j < k. If j = 0, then k divides (a + w)
meant to say (a + 1)
The key idea about this proof is you can offload the work to induction. So for n = 1, 1 divides a + 1 trivially. Then at the n = k + 1 step, assuming n = k holds, you know that 1, ..., k divide the product (a + 1)...(a + k), so clearly they divide the product (a + 1)...(a + k + 1). Use the above argument to show that at exactly one of these terms is divisible by k + 1, you're done

Anonymous

View Same Google iqdb SauceNAO 3eb21d5de6449434d0e480736c5916e0.jpg, 58KiB, 564x959

Anonymous Fri 09 Oct 2020 20:40:54 No.12212599 Report

Quoted By: >>12212634

>>12212516
>The a + n choose n is a positive integer, so it holds. The hard part is seeing it
This is the proof I gave, I know how it works. I was talking about the retarded divisors proof.
>Among k consecutive integers, you can put them in the residue class of k.
Yeah and obviously one of them is going to be 0 mod k. Your wall of text here seems unnecessary.
So you get the product is divisible by k. What now?
>>12212553
>Among k consecutive integers, you can put them in the residue class of k.
Except you're not done. The fact that the product (a+1)...(a+k+1) is divisible by k+1 does not imply (a+1)...(a+k+1)/(1*2*3*...*n) is also divisible by k+1.
Your proof's all retarded, sorry.

Anonymous

Anonymous Fri 09 Oct 2020 20:55:41 No.12212634 Report

Quoted By: >>12212924

>>12212599
>The fact that the product (a+1)...(a+k+1) is divisible by k+1 does not imply (a+1)...(a+k+1)/(1*2*3*...*n)
This takes slightly more work but it's not hard. I never sold this as anything optimal, dumbfuck.

Anonymous

Anonymous Fri 09 Oct 2020 21:20:49 No.12212690 Report

Quoted By: >>12212924

>>12211652
a verbose proof (almost):
1*2*3...*n is a multiple of any of those at least once. Or rather, we can construct it using each of those factors exactly once.
then you need to notice the following pattern:
a+1 is divisible by 1.
(a+1)(a+2) -> one of these two is divisible by 2.
(a+1)(a+2)(a+3) - one of these factors is divisible by 3.
etc.

in (a+1)(a+2)...(a+n), there will be > n/2 of them divisible by 2.
> n/3 divisible by 3
> n/4 divisible by 4

Start with mapping n, then n-1,...

as long as a > 0

still some loose ends, but it's king of, but not really, an interpretation of this:
>>12212292
but without going beyond primary school maths.

Anonymous

View Same Google iqdb SauceNAO ezgif-7-69da05a7346d.gif, 2MiB, 470x352

Anonymous Fri 09 Oct 2020 22:45:15 No.12212924 Report

Quoted By:

>>12212634
>This takes slightly more work but it's not hard
Then do it, faggot. I can't wait to see your proof.
>>12212690
Your proof is incomplete and so not a proof at all. I doubt it's salvageable.

Anonymous

Anonymous Fri 09 Oct 2020 22:52:59 No.12212938 Report

Quoted By:

None of you faggots who claim there's a proof without binomial coefficients have posted your full proof. Still waiting.

Anonymous

Anonymous Sat 10 Oct 2020 13:44:33 No.12214947 Report

Quoted By:

>>12211652

This problem is involved no matter how you solve it.

Solution 1: Binomial Coefficients

Using either strong induction, or an inductive proof that references another inductive proof as a lemma, you can show that the binomial coefficients must be integers.

Solution 2: Prime Factorization

This solution does require lemmas for unique prime factorization, but, once you have them, all you have to do is look at each prime factor, including their multiplicities, and to use both the pigeonhole principle, and the regular distances between sequential pairs of prime factors of the same multiplicity, to argue that any shifted sequence of integers has a greater than, or equal aggregate quantity of primes to an integer sequence of the same length, but starting at 1.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches