HSC 2015 MX1 Marathon (archive) (1 Viewer)

Sy123 · Oct 24, 2015

Re: HSC 2015 3U Marathon

$\\ $Prove by induction or otherwise for integers$ \ n \geq 1 \ $that$ \ n! \leq \left(\frac{n+1}{2} \right)^n$

kawaiipotato · Oct 24, 2015

Re: HSC 2015 3U Marathon

Sy123 said:
$\\ $Prove by induction or otherwise for integers$ \ n \geq 1 \ $that$ \ n! \leq \left(\frac{n+1}{2} \right)^n$

$\underline{$For n=1 and n=2$}$

$$LHS$ = 1! = 1$
$$RHS$ = \left(\frac{1+1}{2}\right)^{2} = 1 = LHS$
$Equality for n = 1$

$$LHS$ = 2! = 2$
$RHS$ = \left(\frac{2+1}{2}\right)^{2} = 2.25 > $LHS$

$\therefore $equality for n=1 and inequality for n=2$$

$\underline{$Assume true for n=k$}$

$k! \leq \left(\frac{k+1}{2}\right)^{k}$

$For n = k+1, prove$

$(k+1)! \leq \left(\frac{k+2}{2}\right)^{k+1}$

$$LHS$ = (k+1)! = (k+1) k!$

$\leq (k+1)\left(\frac{k+1}{2}\right)^{k} ($By the assumption$)$

$= \frac{(k+1)^{k+1}}{2^{k}}$

$$Aim:$ \left(\frac{k+2}{2}\right)^{k+1} \geq \frac{(k+1)^{k+1}}{2^{k}}$

$$Consider$ \left(\frac{k+2}{k+1}\right)^{k+1}$

$n \geq 1 \Rightarrow k \geq 1$

$k+1 \geq 2 $and$ k+2 \geq 3$

$\therefore \left(\frac{k+2}{k+1}\right)^{k+1} \geq 2.25 > 2$

$\therefore \left(\frac{k+2}{2}\right)^{k+1} \geq \frac{(k+1)^{k+1}}{2^{k}}$

$\geq (k+1)!$

$True for n=k+1$

godofindolence · Oct 24, 2015

Re: HSC 2015 3U Marathon

rand_althor said:
$$1. The real number $x$ is a solution of the equation $x^2-x-1=0$. Use the Binomial Theorem to show that the sum $S$ of the series $1+x+x^2+...+x^{2n-1}$ ($n=1,2,3...$) is given by $S=\sum^n_{r=1}\binom{n}{r}x^{r+1}$.$

$$2. (i) Show that $\binom{n}{r}=\binom{n}{n-r}$ for $r=0,1,2,3,...,n$. \\ \indent (ii) Let $f(r)=\binom{n}{0}\binom{n}{r} + \binom{n}{1}\binom{n}{r+1} + \binom{n}{2}\binom{n}{r+2} +...+ \binom{n}{n-r}\binom{n}{n}$ for $r=0,1,2,...,n$. By considering the coefficient of $x^{n-r}$ in the expansions of $(1+x)^{2n}$ and $(1+x)^n(1+x)^n$ show that $f(r)=\binom{2n}{n-r}$. \\ \indent (iii) Show that $\binom{n}{0}f(0) + \binom{n}{1}f(1) + \binom{n}{2}f(2) + ... + \binom{n}{n}f(n)=\binom{3n}{n}$.$

These are beyond me, anyone else?

InteGrand · Oct 24, 2015

Re: HSC 2015 3U Marathon

godofindolence said:
These are beyond me, anyone else?

The first one was answered on a thread here:

InteGrand said:
$Note that $x$ isn't an arbitrary variable here, rather, it refers to a number that satisfies $x^2 - x - 1 = 0$ (there are two such $x$, but it is unnecessary to find what they are). From this equation, we know that $x^2 = x+1$ and $x(x-1) = x^2 -x = 1$ (we will use these facts) later. Let the series be $S_1 = 1 + x + x^2 + \cdots + x^{2n-1}$. Note that clearly $x\neq 1$, so by the sum of a geometric series formula, we have $S_1 = \frac{x^{2n}-1}{x-1}\Rightarrow (x-1)S_1 = x^{2n}-1$ (note that this geometric series formula is not valid if the common ratio is 1, which is why we made clear that $x$, the common ratio, is not 1 (it can't be 1 because 1 does not satisfy the equation that $x$ satisfies)). We have$

$$S=\sum_{r=1}^n \binom{n}{r}x^{r+1}=x\left(\sum_{r=1}^n \binom{n}{r}x^{r}\right)$ (factoring out one $x$)$

$$=x\left(\sum_{r=0}^n \binom{n}{r}x^{r} -1\right)$ (starting the sum from $r=0$ and subtracting 1 to compensate, since putting in the $r=0$ term means we have added 1 to the series, because the $r=0$ term is 1)$

$$=x\left((1+x)^n -1\right)$ (binomial theorem)$

$$=x\left((x^2)^n -1\right)$ (as we are given that $1+x = x^2$)$

$$=x\left(x^{2n}-1\right)$ (index laws)$

$$=x(x-1)S_1$ (since we showed that $(x-1)S_1 = x^{2n}-1$)$

$$=S_1$ (since we showed that $x(x-1)=1$)$

$and so $S_1$ is given by the sum $S$. $\blacksquare$$

davidgoes4wce · Oct 24, 2015

Re: HSC 2015 3U Marathon

I had a go at an induction inequality.

I haven't quite finished with the statements but I am basing my method on the Kinney-Lewis method. ( I know there are many methods by which you could do these questions).

Not sure if I have the last step right but my thinking is if k^2+3k, if k greater than or equal to 4, the statement is true.

InteGrand · Oct 24, 2015

Re: HSC 2015 3U Marathon

davidgoes4wce said:
I had a go at an induction inequality.

I haven't quite finished with the statements but I am basing my method on the Kinney-Lewis method. ( I know there are many methods by which you could do these questions).

Not sure if I have the last step right but my thinking is if k^2+3k, if k greater than or equal to 4, the statement is true.

$Yeah, if $k\geq 4$, then clearly $k^2 + 3k \geq 4^2 + 3\times 4 >0$, and $2^{k+3}$ is positive always, so that product in the last line is positive, and thus that inequality in the last line holds.$

davidgoes4wce · Oct 24, 2015

Re: HSC 2015 3U Marathon

^^^ I should say the question is for all integers for n, greater than or equal to 4 as well.

Sy123 · Oct 24, 2015

Re: HSC 2015 3U Marathon

kawaiipotato said:
$$Consider$ \left(\frac{k+2}{k+1}\right)^{k+1}$

$n \geq 1 \Rightarrow k \geq 1$

$k+1 \geq 2 $and$ k+2 \geq 3$

$\therefore \left(\frac{k+2}{k+1}\right)^{k+1} \geq 2.25 > 2$

$\therefore \left(\frac{k+2}{2}\right)^{k+1} \geq \frac{(k+1)^{k+1}}{2^{k}}$

$\geq (k+1)!$

$True for n=k+1$

On track up to this part, your proof of this is not valid

Just because $a \geq b \ $and$ \ c \geq d$ does not mean $\frac{a}{c} \geq \frac{b}{d}$ (which is what you do when you divide the inequalities (k+2) > 3 and (k+1) > 2)

For instance, $4 > 3$ and $3 > 2$ but $\frac{4}{3} < \frac{3}{2}$

davidgoes4wce · Oct 24, 2015

Re: HSC 2015 3U Marathon

I'll have a go doing the question kawaii and Sy123 last answered doing my way then.

kawaiipotato · Oct 24, 2015

Re: HSC 2015 3U Marathon

Sy123 said:
On track up to this part, your proof of this is not valid

Just because $a \geq b \ $and$ \ c \geq d$ does not mean $\frac{a}{c} \geq \frac{b}{d}$ (which is what you do when you divide the inequalities (k+2) > 3 and (k+1) > 2)

For instance, $4 > 3$ and $3 > 2$ but $\frac{4}{3} < \frac{3}{2}$

That's true. How about this then:
$\frac{k+2}{k+1}$

$= \frac{k+1}{k+1} + \frac{1}{k+1}$

$$ Since $ k+1 \geq 2$

$\frac{1}{k+1} \leq \frac{1}{2}$

$\frac{1}{k+1} + \frac{k+1}{k+1} = \frac{k+2}{k+1} \geq 1.5$

$\left(\frac{k+2}{k+1}\right)^{k+1} \geq 2.25$

Sy123 · Oct 24, 2015

Re: HSC 2015 3U Marathon

rand_althor said:
$$2. (i) Show that $\binom{n}{r}=\binom{n}{n-r}$ for $r=0,1,2,3,...,n$. \\ \indent (ii) Let $f(r)=\binom{n}{0}\binom{n}{r} + \binom{n}{1}\binom{n}{r+1} + \binom{n}{2}\binom{n}{r+2} +...+ \binom{n}{n-r}\binom{n}{n}$ for $r=0,1,2,...,n$. By considering the coefficient of $x^{n-r}$ in the expansions of $(1+x)^{2n}$ and $(1+x)^n(1+x)^n$ show that $f(r)=\binom{2n}{n-r}$. \\ \indent (iii) Show that $\binom{n}{0}f(0) + \binom{n}{1}f(1) + \binom{n}{2}f(2) + ... + \binom{n}{n}f(n)=\binom{3n}{n}$.$

$\\ $i) Using the definition$ \ \binom{n}{r} := \frac{n!}{(n-r)!r!} \\ $So,$ \ \binom{n}{r} = \frac{n!}{(n-r)! r!} = \frac{n!}{(n- (n-r))! (n-r)!} = \binom{n}{n-r}$

$\\ $ii) Transform the expression$ \ f(r) \ $into an easier to deal form, that is, replace every$ \ \binom{n}{r+k} \ $with$ \ \binom{n}{n - (r+k)}$

$\\ $So,$ \ f(r) = \binom{n}{0} \binom{n}{n-r} + \binom{n}{1} \binom{n}{n - r - 1} + \binom{n}{2} \binom{n -r - 2} + \dots + \binom{n}{n-r} \binom{0}$

$\\ $Consider the co-efficient of$ \ x^{n-r} \ $on both sides of the equation$ \ (1+x)^{2n} = (1+x)^n (1+x)^n \\\\ $On the left-hand-side the co-efficient is$ \ \binom{2n}{n-r}$

$\\ $On the right-hand-side, the co-efficient is arrived at by taking the coefficient of$ \ x^k \ $from the first$ \ (1+x)^n \ $and$ \ x^{n-r-k} \ $from the second$ \ (1+x)^n \ $for all$ \ k = 0,1,2, \dots, n-r$

$\\ $So,$ \ \binom{2n}{n-r} = \sum_{k=0}^{n-r} \underbrace{\binom{n}{k} \binom{n}{n-r-k}}_{\text{Take} \ k \ \text{from the first bracket, and} \ n-r-k \ \text{from the second}}$

$\\ f(r) = \sum_{k=0}^{n-r}$

$\Rightarrow \ f(r) = \binom{2n}{n-r}$

$\\ $iii) Consider the coefficient of$ \ x^n \ $in the expression$ \ (1+x)^{3n} = (1+x)^n (1+x)^{2n}$

$\\ $Take$ \ x^k \ $from the first bracket, and$ \ x^{n-k} \ $from the second one, meaning$ \ \binom{3n}{n} = \sum_{k=0}^n \binom{n}{k} \binom{2n}{n-k} = \sum_{k=0}^n \binom{n}{k} f(k)$

Mikes · Oct 24, 2015

Re: HSC 2015 3U Marathon

godofindolence said:
http://puu.sh/kVD1b/237ba30933.JPG
You got any of that binomials?

Could you explain your part (iii)?

Sy123 · Oct 24, 2015

Re: HSC 2015 3U Marathon

kawaiipotato said:
$\frac{1}{k+1} \leq \frac{1}{2}$

$\frac{1}{k+1} + \frac{k+1}{k+1} = \frac{k+2}{k+1} \geq 1.5$
[/tex]

The addition here is the wrong way around

davidgoes4wce · Oct 24, 2015

Re: HSC 2015 3U Marathon

kawaiipotato said:
$\underline{$For n=1 and n=2$}$

$$LHS$ = 1! = 1$
$$RHS$ = \left(\frac{1+1}{2}\right)^{2} = 1 = LHS$
$Equality for n = 1$

$$LHS$ = 2! = 2$
$RHS$ = \left(\frac{2+1}{2}\right)^{2} = 2.25 > $LHS$

$\therefore $equality for n=1 and inequality for n=2$$

$\underline{$Assume true for n=k$}$

$k! \leq \left(\frac{k+1}{2}\right)^{k}$

$For n = k+1, prove$

$(k+1)! \leq \left(\frac{k+2}{2}\right)^{k+1}$

$$LHS$ = (k+1)! = (k+1) k!$

$\leq (k+1)\left(\frac{k+1}{2}\right)^{k} ($By the assumption$)$

$= \frac{(k+1)^{k+1}}{2^{k}}$

$$Aim:$ \left(\frac{k+2}{2}\right)^{k+1} \geq \frac{(k+1)^{k+1}}{2^{k}}$

$$Consider$ \left(\frac{k+2}{k+1}\right)^{k+1}$

$n \geq 1 \Rightarrow k \geq 1$

$k+1 \geq 2 $and$ k+2 \geq 3$

$\therefore \left(\frac{k+2}{k+1}\right)^{k+1} \geq 2.25 > 2$

$\therefore \left(\frac{k+2}{2}\right)^{k+1} \geq \frac{(k+1)^{k+1}}{2^{k}}$

$\geq (k+1)!$

$True for n=k+1$

Its the first time I have seen an Induction question done where you have substituted 2 constants in.

davidgoes4wce · Oct 24, 2015

Re: HSC 2015 3U Marathon

I had a go at the question kawaii answered using the Kinney-Lewis method but Im not sure if that last line is good enough to get the full marks. (Again I havent included my statements in)

Sy123 · Oct 24, 2015

Re: HSC 2015 3U Marathon

davidgoes4wce said:
I had a go at the question kawaii answered using the Kinney-Lewis method but Im not sure if that last line is good enough to get the full marks. (Again I havent included my statements in)

It wouldn't receive full marks unless you prove that last line as it isn't an immediate result

I'll post my solution soon

godofindolence · Oct 24, 2015

Re: HSC 2015 3U Marathon

Mikes said:
Could you explain your part (iii)?

From part 2 we know that 1/n! < 1/e^n but this only occurs at n is bigger or equal to 6.
So when you replace n in the above inequality with 6,7,8,9... etc, this will give you the relationship on the left, plus the first 5 terms which is smaller than those on the right plus the first 5 terms.

Sy123 · Oct 24, 2015

Re: HSC 2015 3U Marathon

Sy123 said:
$\\ $Prove by induction or otherwise for integers$ \ n \geq 1 \ $that$ \ n! \leq \left(\frac{n+1}{2} \right)^n$

As kawaiipotato has proven, one needs to only prove:

$\frac{(k+1)^{k+1}}{2^k} \leq \left(\frac{k+2}{2} \right)^{k+1}$

We can re-arrange it and cancel out the denominators, to proving:

$\\ $Prove that$ \ \left(\frac{k+2}{k+1} \right)^{k+1} > 2$

$\\ $So,$ \ \left(\frac{k+2}{k+1} \right)^{k+1} = \left(1 + \frac{1}{k+1} \right)^{k+1}$

$\\ $Then, expand using the binomial theorem$

$\\ \left(1 + \frac{1}{k+1} \right)^{k+1} = \binom{k+1}{0} + \binom{k+1}{1} \frac{1}{k+1} + \binom{k+1}{2} \frac{1}{(k+1)^2} + \dots + \binom{k+1}{k+1} \frac{1}{(k+1)^{k+1}}\\ \\ = 1 + 1 + C \ $for some$ \ C > 0 \ $(they are simply the terms of the expansion except for the first two ones which simplify to those 1s)$$

$\\ \left(1 + \frac{1}{k+1} \right)^{k+1} = 2 + C > 2 \ $as$ \ C > 0$

$\\ $Therefore$ \ \frac{(k+1)^{k+1}}{2^k} \leq \left(\frac{k+2}{2} \right)^{k+1}$

$\\ $So, the inductive step is complete$$

davidgoes4wce · Oct 25, 2015

Re: HSC 2015 3U Marathon

Sy123 said:
As kawaiipotato has proven, one needs to only prove:

$\frac{(k+1)^{k+1}}{2^k} \leq \left(\frac{k+2}{2} \right)^{k+1}$

We can re-arrange it and cancel out the denominators, to proving:

$\\ $Prove that$ \ \left(\frac{k+2}{k+1} \right)^{k+1} > 2$

$\\ $So,$ \ \left(\frac{k+2}{k+1} \right)^{k+1} = \left(1 + \frac{1}{k+1} \right)^{k+1}$

$\\ $Then, expand using the binomial theorem$

$\\ \left(1 + \frac{1}{k+1} \right)^{k+1} = \binom{k+1}{0} + \binom{k+1}{1} \frac{1}{k+1} + \binom{k+1}{2} \frac{1}{(k+1)^2} + \dots + \binom{k+1}{k+1} \frac{1}{(k+1)^{k+1}}\\ \\ = 1 + 1 + C \ $for some$ \ C > 0 \ $(they are simply the terms of the expansion except for the first two ones which simplify to those 1s)$$

$\\ \left(1 + \frac{1}{k+1} \right)^{k+1} = 2 + C > 2 \ $as$ \ C > 0$

$\\ $Therefore$ \ \frac{(k+1)^{k+1}}{2^k} \leq \left(\frac{k+2}{2} \right)^{k+1}$

$\\ $So, the inductive step is complete$$

Why is the 2nd line '>2'. Im assuming you are substituting k=1 in?

InteGrand · Oct 25, 2015

Re: HSC 2015 3U Marathon

davidgoes4wce said:
Why is the 2nd line '>2'.

It's just a rearrangement of the preceding line.

HSC 2015 MX1 Marathon (archive) (1 Viewer)

This too shall pass

Well-Known Member

Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

This too shall pass

Well-Known Member

Well-Known Member

This too shall pass

Member

This too shall pass

Well-Known Member

Well-Known Member

This too shall pass

Member

This too shall pass

Well-Known Member

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)