Author Topic: TT's Maths Thread (Read 146540 times) Tweet Share

Ahmad · « **Reply #60 on:** November 14, 2009, 10:05:05 pm »

Let $1 \le x, y, z \le n$ be integers with z being the largest (but not strictly) of the 3, how many such tuples (x,y,z) are there which satisfy this condition?

Well if z = 1 then there's only 1 choice for x, notably x = 1 and similarly 1 choice for y, notably y = 1, giving 1^2 possibilities. If z = 2, then there are 2 choices for x and 2 choices for y, giving 2^2 possibilities. Continuing in this manner, in total there are $1^2 + 2^2 + \cdots + n^2$ such tuples.

But we can also count this another way by dividing this into cases.

x = y = z: C(n, 1) = n ways
x = y < z: We can pick any 2 integers from 1 to n and the larger we assign to z, the smaller we assign to x = y. C(n,2) possibilities here.
x < y = z or y < x = z: C(n, 2) ways each, similar reasoning to above
x < y < z or y < x < z: We can pick any 3 integers from 1 to n, and assign them to x, y, z based on their size. C(n, 3) possibilities each here.

Hence we've counted the same quantity in 2 ways, so $1^2 + 2^2 + \cdots + n^2 = \binom{n}{1} + 3 \binom{n}{2} + 2 \binom{n}{3} = \frac{n(n+\frac{1}{2})(n+1)}{3}$

dcc · « **Reply #61 on:** November 14, 2009, 10:06:12 pm »

By popular request, I'll also show the induction proof (which assumes for some reason that you know the answer!)

Let $P(n)$ be the statement that $\sum_{k=1}^n k^2 = \frac{1}{6}n\left(n+1\right)(2n+1)$ .

Base Case:

Consider $P(1)$ . $\sum_{k=1}^1 k^2 = 1$ , $\frac{1}{6}\cdot 1 \cdot 2 \cdot 3 = 1$ , hence $P(1)$ is true.

Inductive Step:

Assume $P(m)$ is true for some positive integer $m$ . Therefore we know that:

$\sum_{k=1}^m k^2 = \frac{1}{6}m\left(m+1\right)\left(2m+1\right)$

Adding $\left(m + 1\right)^2$ to each side of this expression, we find:

$\begin{align*} \sum_{k=1}^m k^2 + \left(m + 1\right)^2 &= \frac{1}{6}m\left(m + 1\right)\left(2m+1\right) + \left(m + 1\right)^2\\ \sum_{k=1}^{m+1} k^2 &= \left(m + 1\right) \left( \frac{1}{6}m\left(2m + 1\right) + \left(m + 1\right) \right)\\ &= \frac{1}{6} \left(m+1\right) \left(m(2m + 1) + 6(m + 1)\right)\\ &= \frac{1}{6} \left(m + 1\right) \left(2m^2 + 7m + 6\right)\\ &= \frac{1}{6} \left(m + 1\right) \left(m + 2\right)\left(2m + 3\right)\\ &= \frac{1}{6} \left(m + 1\right) \left(\left(m + 1\right) + 1\right)\left(2(m + 1) + 1\right)\\ \end{align*}$

This is precisely the expression we were hoping to attain to show $P(m+1)$ . Hence $P(m) \implies P(m + 1)$ .

Therefore by the principle of mathematical induction, $P(n)$ is true for all positive integers $n$ .

TrueTears · « **Reply #62 on:** November 14, 2009, 10:16:12 pm »

Thanks so much! That really clears it all up.

Just started on induction and summations today, so I wasn't really sure how to approach these questions. That really helped!

kamil9876 · « **Reply #63 on:** November 14, 2009, 10:25:53 pm »

lol i remember running into a method that's similair to ahmad's but more complicated when realising that a marble counting problem can be solved in two different ways. http://vcenotes.com/forum/index.php/topic,13271.msg171784.html#msg171784

TrueTears · « **Reply #64 on:** November 14, 2009, 11:59:09 pm »

An exercise dcc gave me: Find a formula for $\sum_{k=1}^n k^3$

There are probs plenty of better methods but this is the one I've learnt so far...

First remember the result $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$

Now to find $\sum_{k=1}^n k^3$ we need to find some polynomial containing $k^3$ .

So let $u_{k+1} - u_k = \mbox{some polynomial with} \ k^3$

Now let $u_k = k^4$

Thus $u_{k+1} - u_k = (k+1)^4 - k^4$

Now $\sum_{k=1}^n u_{k+1} - u_k = u_2 - u_1 + u_3 - u_2 + ... + u_{n+1} - u_n = u_{n+1} - u_1 = (n+1)^4 - 1$

But $\sum_{k=1}^n (k+1)^4 - k^4 = \sum_{k=1}^n (4k^3 + 6k^2 + 4k+1)$

$\implies \sum_{k=1}^n 4k^3 + 6k^2 + 4k+1 = (n+1)^4 - 1$

$\implies 4\sum_{k=1}^n k^3 = (n+1)^4 - 1 - 6\sum_{k=1}^n k^2 - \sum_{k=1}^n (4k+1)$

$\implies 4\sum_{k=1}^n k^3 = (n+1)^4 - 1 - n(n+1)(2n+1) - \frac{n}{2}(5+4n+1)$

$\therefore \sum_{k=1}^n k^3 = \frac{n^2}{4}\left(n^2+2n+1\right)$

I can see using this method to find something like $\sum_{k=1}^n k^{100}$ would be super tedious haha

TrueTears · « **Reply #65 on:** November 15, 2009, 02:55:32 am »

Alright another Q, I think the book *might* be wrong with this question...

The Zeta function $Z(s)$ is defined by the infinite series $Z(s) = \frac{1}{1^s} + \frac{1}{2^s} + \frac{1}{3^s} + ...$

When $s = 1$ , this becomes the harmonic series and diverges. Show that $Z(s)$ converges for all $s \ge 2$

My working:

If we can show that for $s = 2$ then $Z(s)$ converges then for $s > 2$ will converge as well.

The general sum for $s = 2$ is $\sum_{k=1}^n \frac{1}{k^2}$

So we need to prove that $\sum_{k=1}^n \frac{1}{k^2}$ converges.

Now using telescoping we find $\sum_{k=1}^n \frac{1}{k^2+k} = 1 - \frac{1}{n+1}$ (The proof is fairly easy)

However we need to find something similar to $\frac{1}{k^2-k}$ instead of $\frac{1}{k^2+k}$ since using comparison, if we compare $\sum_{k=1}^n \frac{1}{k^2}$ to a larger converging series, that means $\sum_{k=1}^n \frac{1}{k^2}$ is converging. This "larger series" we are looking for should be of the form $\sum_{k=a}^b \frac{1}{k^2-k}$ with some limits $a$ or $b$ .

Now what are these limits? Using change of index we find that $\sum_{k=1}^n \frac{1}{k^2+k} = \sum_{k=2}^{n+1} \frac{1}{k^2-k}$

This is where I think the first mistake is because book has $\sum_{k=1}^n \frac{1}{k^2+k} = \frac{1}{2} + \sum_{k=2}^{n+1} \frac{1}{k^2-k}$ . Where did $\frac{1}{2}$ come from? Mistake?

Now since $\frac{1}{k^2} < \frac{1}{k^2-k}$

Taking the summation of both sides from 1 to n yields:

$\sum_{k=1}^n \frac{1}{k^2} < \sum_{k=1}^n \frac{1}{k^2-k}$

But this will leave the RHS undefined so WLOG we require:

$\sum_{k=2}^n \frac{1}{k^2} < \sum_{k=2}^n \frac{1}{k^2-k}$

Now we need to find a formula for the RHS.

We know that $\sum_{k=2}^{n+1} \frac{1}{k^2-k} = \sum_{k=1}^n \frac{1}{k^2+k} = \frac{1}{2} + \frac{1}{6} + \frac{1}{12} + ... + \frac{1}{n^2-n} + \frac{1}{n^2+n}$

And we also know $\sum_{k=2}^n \frac{1}{k^2-k} = \frac{1}{2} + \frac{1}{6} + \frac{1}{12} + ... + \frac{1}{n^2-n}$

$\implies \sum_{k=2}^n \frac{1}{k^2-k} = \sum_{k=1}^{n} \left(\frac{1}{k^2+k}\right) - \frac{1}{n^2+n}$

$\implies \sum_{k=2}^n \frac{1}{k^2-k} = 1 - \frac{1}{n+1} - \frac{1}{n^2+n}$

$\implies \sum_{k=2}^n \frac{1}{k^2-k} = 1 - \frac{1}{n}$

$\therefore \sum_{k=2}^n \frac{1}{k^2} < 1 - \frac{1}{n}$ Which means it is converging.

However book's last line is $\therefore \sum_{k=2}^n \frac{1}{k^2} < 1 - \frac{1}{n+1}$

Where did the $n+1$ on the denominator come from?

Thanks.

Last few questions for the night.

1. Find a formula for the sum $\sum_{k=1}^n \frac{k}{(k+1)!}$

2. Find the sum of $\sum_{k=2}^n \left(\frac{1}{\log_k(u)}\right)$

Many thanks!

dcc · « **Reply #66 on:** November 15, 2009, 10:25:27 am »

2. Evaluate $\sum_{k=2}^n \left(\frac{1}{\log_{k}(u)}\right)$

Let $S(u) = \sum_{k=2}^n \left(\frac{1}{\log_{k}(u)}\right) = \sum_{k=2}^n \left( \frac{1}{\frac{\log(u)}{\log(k)}} \right)$

Hence $S(u) = \frac{1}{\log(u)} \left( \sum_{k=2}^n \log(k) \right) = \frac{\log(n!)}{\log(u)} = \log_u(n!)$

By our logarithm laws.

TrueTears · « **Reply #67 on:** November 15, 2009, 03:02:05 pm »

Quote from: dcc on November 15, 2009, 10:25:27 am

2. Evaluate $\sum_{k=2}^n \left(\frac{1}{\log_{k}(u)}\right)$

Let $S(u) = \sum_{k=2}^n \left(\frac{1}{\log_{k}(u)}\right) = \sum_{k=2}^n \left( \frac{1}{\frac{\log(u)}{\log(k)}} \right)$

Hence $S(u) = \frac{1}{\log(u)} \left( \sum_{k=2}^n \log(k) \right) = \frac{\log(n!)}{\log(u)} = \log_u(n!)$

By our logarithm laws.

Thanks dcc, so elegant!

TrueTears · « **Reply #68 on:** November 15, 2009, 03:40:02 pm »

Quote

1. Find a formula for the sum $\sum_{k=1}^n \frac{k}{(k+1)!}$

I've tried telescoping this one a bit and I've got to:

Let $f(x) = \frac{k}{(k+1)!}$

Thus we need to find some expression $u_{k+1} - u_{k} = f(x)$

Let $u_k = \frac{1}{k!}$

$\implies u_{k+1} = \frac{1}{(k+1)!}$

$\therefore \frac{1}{(k+1)!} - \frac{1}{k!} = \frac{-k}{(k+1)!}$

Which is close but there is a negative on the $k$ .

So why not try $u_k - u_{k+1}$ ? This leads to:

$\frac{1}{k!} - \frac{1}{(k+1)!} = \frac{k}{(k+1)!}$ which is what we want.

Thus $\sum_{k=1}^n f(x) = \sum_{k=1}^n \frac{1}{k!} - \sum_{k=1}^n \frac{1}{(k+1)!}$

And then... I'm stuck, how do you go about evaluating those 2 sums?

Basically I think if I can get the first sum then the second one will follow, since it is just $\sum_{k=1}^n \frac{1}{(k+1)k!}$ , but how to get the first one lol

It looks awfully similar to Taylor's series for $\textrm{e}^x \approx 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots + \frac{x^n}{n!}$ ...

But it is just an approximation for $e^x$ , so can I use it?

kamil9876 · « **Reply #69 on:** November 15, 2009, 03:53:09 pm »

You did all the hard work, but got confused by some notation.

So you found that. $u_{k+1} - u_k=a_k$ where the sum we're after is the sum of $a_i$ .

therefore:

$f(k)=a_1+a_2+a_3+...a_k=u_{k+1}-u_1$

edit: basically $u_k=\frac{-1}{k!}$ (another way to handle that negative you initially got

)

TrueTears · « **Reply #70 on:** November 15, 2009, 04:02:23 pm »

Quote from: kamil9876 on November 15, 2009, 03:53:09 pm

You did all the hard work, but got confused by some notation.

So you found that. $u_{k+1} - u_k=a_k$ where the sum we're after is the sum of $a_i$ .

therefore:

$f(k)=a_1+a_2+a_3+...a_k=u_{k+1}-u_1$

edit: basically $u_k=\frac{-1}{k!}$ (another way to handle that negative you initially got )

hahaha thanks I think I got it.

kk so let $u_k = \frac{-1}{k!}$

$\implies u_{k+1} = \frac{-1}{(k+1)!}$

Thus $u_{k+1} - u_k = \frac{k}{(k+1)!}$ which is what we want!

$\therefore \sum_{k=1}^n \frac{1}{k!} - \frac{1}{(k+1)!} = \sum_{k=1}^n u_{k+1} - u_k = u_2 - u_1 + u_3 - u_2 + ... + u_{n+1} - u_n = u_{n+1} - u_1$

So $\sum_{k=1}^n \frac{k}{(k+1)!} = u_{n+1} - u_1 = 1 - \frac{1}{(n+1)!}$

I <3 telescoping

TrueTears · « **Reply #71 on:** November 15, 2009, 04:17:52 pm »

I just realised something else

Using Taylor's series:

$\textrm{e}^x \approx 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots + \frac{x^n}{n!}$

Let $x = 1$

Thus $e - 1 = 1 + \frac{1}{2!} + \frac{1}{3!} + ... + \frac{1}{n!}$

Which follows on from my previous working: $\sum_{k=1}^n f(x) = \sum_{k=1}^n \frac{1}{k!} - \sum_{k=1}^n \frac{1}{(k+1)!}$

Since $\sum_{k=1}^n \frac{1}{k!} = 1 + \frac{1}{2!} + \frac{1}{3!} + ... + \frac{1}{n!} = e - 1$

and $\sum_{k=1}^n \frac{1}{(k+1)!} = \sum_{k=1}^n \frac{1}{(k+1)k!} = \frac{1}{2} + \frac{1}{(3)(2!)} + \frac{1}{(4)(3!)} + ... + \frac{1}{(n+1)n!} = \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + ... +\frac{1}{(n+1)!} = e - 2$

$\therefore$ $\sum_{k=1}^n f(x) = \sum_{k=1}^n \frac{1}{k!} - \sum_{k=1}^n \frac{1}{(k+1)!} = e - 1 - (e-2) = 1$

kamil9876 · « **Reply #72 on:** November 15, 2009, 04:27:56 pm »

as n approaches infinity

Which you found from formula in previous post

TrueTears · « **Reply #73 on:** November 15, 2009, 05:11:01 pm »

Thanks kamil

Another one: Find a formula for $\frac{1}{1 \times 2 \times 3} + \frac{1}{2 \times 3 \times 4} + ... + \frac{1}{n \times (n+1) \times (n+2)}$

So we require $\sum_{k=1}^n \left(\frac{1}{k(k+1)(k+2)}\right) = \sum_{k=1}^n \left( \frac{1}{2(k+2)} + \frac{1}{2k} - \frac{1}{k+1} \right)$

I tried telescoping this one:

$\sum_{k=1}^n \left( \frac{1}{2k} - \frac{1}{k+1} \right)$

since it looks very similar to $\sum_{k=1}^n \left(\frac{1}{k} - \frac{1}{k+1}\right) = 1 - \frac{1}{n-1}$ but doesn't seem to work...

Any hints/help?

kamil9876 · « **Reply #74 on:** November 15, 2009, 05:19:05 pm »

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

$=\frac{1}{u_{k+1}}-\frac{1}{u_k} + \frac{1}{2}(\frac{1}{k} - \frac{1}{k+1})$

So you're better off splitting your sum into these to, since the way you have splitted up you may end up evaluating $\infty - \infty$ . (ie the difference between two sequences who both limit to infinity)

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 146540 times) Tweet Share

Ahmad

Re: TT's Maths Thread

dcc

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

dcc

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

Recent Posts

User:
Password: