Question

Question about binomial theorem is in comments (due to a need of correct markup).

Answer 1

This isn't necessarily true. Consider \(n=1\) and \(k=0\).

Answer 2

\[\left(\begin{matrix}n \\ k\end{matrix}\right)<\left(\begin{matrix}n \\ k+1\end{matrix}\right)\]
if and only if 0 <= k < 1/2(n-1)

Answer 3

Sorry, @HolsterEmission, it seems that another post of mine, where I tell that it is 0 <= k < 1/2(n-1) did not send.

Answer 4

n! n!
---- < -------
k!(n-k)! (k+1)! (n - k -1)!

k!(n-k)! > k+1)! (n - k -1)!

we should be able to get a relation between k and n from this.

Answer 5

@welshfella should we take the base as k or as n? This time I am confused because of two letters...

Answer 6

Hey, what's the question ?

Answer 7

I'm taking it to be Zybergs first post...

Answer 8

- proof of that inequality

Answer 9

Oh I see... nice :)

Answer 10

k!(n-k)! > (k+1)! (n - k -1)!

simplifying above should do yeah

Answer 11

k!(n-k)! > (k+1)! (n - k -1)!
k!(n-k)! > k!(k+1) (n-k-1)!
(n - k)! > (k+1)(n - k - 1)!
Now right the left side as (n-k)(n - k - 1)! and you are nearly done.

Answer 12

Oh, so it won't even require real induction? The thing that is confusing me is that I usually have to use induction on theorems that have only one unknown...

Answer 13

@ganeshie8 it's from "Elementary Numbers Theory" book, you recommended to me ;)

Answer 14

I think we may use induction by inducting on "n"

Answer 15

You may start by proving the given statement is true for n=3

Answer 16

Notice that we're not interested in n < 3 because there is not integer "k" that satisfies the given condition 0 <= k < 1/2(n-1) when n < 3.

Answer 17

Yes, I tried to do that, but then I need to set up a value for k too, yes? How would that work with induction step then? (I understand setting base to be n = 3, k = 0)

Answer 18

You don't have to worry about "k" at all as we're inducting on "n"

Answer 19

Let me say again, we're inducting on "n", not k.

Answer 20

But placing the value of n = 3 would get us:
(3-k)! > (k+1)(2-k)!, how would we check, if it's true then?

Answer 21

Without knowing k, is it possible to rework (2-k)! somehow, to prove to be true?

Answer 22

use the given condition :
0 <= k < 1/2(n-1)

plugin n=3 and see what values of "k" we must check

Answer 23

But wouldn't that account as "worrying" for k? k would become 0, but what about induction step? What k would be for n = r? n = r+1?

Answer 24

We are still not worrying about "k" as part of the induction process :
step1) show the statement is true for n=3
step2) assume that the statement is true for n = r
step3) prove the statement is trur for n = r+1 whenever step2 is true.

Answer 25

For n=r, we assume that the given statement is true for all "k" that satisfy 0 <= k < 1/2(r-1)

Answer 26

We just have to follow the rules when using induction to prove

Answer 27

Proof happens pretty much automatically

Answer 28

so:
(t - k)! > (k+1)(t - k - 1)!
Multiplying by t - k + 1 or something like that?

Answer 29

Yep, also note that we're only proving below part :

If 0 <= k < 1/2(n-1), then \(\left(\begin{matrix}n \\ k\end{matrix}\right)<\left(\begin{matrix}n \\ k+1\end{matrix}\right)\).

Answer 30

We need to prove the converse of that too

Answer 31

Ah yes that is what I was attempting to do - the converse.

Answer 32

i misread the question really

Answer 33

You are right about that... wouldn't have thought of it ;) But how would we prove converse of that?

Answer 34

I think if you further simplify:
(n - k)! > (k+1)(n - k - 1)!
(n-k)(n-k-1)! > (k+1)(n ik-1)!
n - k > k + 1
k < (1/2)(n- 1)

Answer 35

and therefore 0 <= k < 1/2(n-1)

Answer 36

Okay, thank you very much! :) I think that I need a break now, for not noticing that... Ehh! Thank you for help as well, @ganeshie8! Decided to finish the book until the end of the year and so far it's quite fun (though I have been jumping all around of it and only now I started doing things systematically).

Answer 37

yw
I'm going for a break too!

Answer 38

Its my favorite book on NT. Good to see you're enjoying it too :)