Discrete Mathematics summation evaluation.?

Question

I don't know what my teacher is asking in this problem

Evaluate the summation from k=0 to n/2 (n 2k).

Thanks in advance.

(n 2k)
that is not multiplication it's a large parentheses with n at the top and 2k at the bottom. Looks like a fraction without the bar in the middle.

Answer 1

Edit: okay, now I see what you are talking about. That "large parentheses" represents the binomial coefficient, where (n k) = n!/(k!(n-k)!). So your teacher is asking you to evaluate [k=0, n/2]∑n!/(k!(n-k)!). Basically, this is the sum of every other number in the nth row of Pascal's triangle (e.g. for n=4, the fourth row of my triangle is 1 4 6 4 1, so this would be 1+6+1). You will note that each number in the triangle is simply the sum of the two numbers directly above it, and that by counting every other number, you count each number in the row directly above only once. Thus, the sum will be the sum of all the numbers in the (n-1)th row, which is 2^(n-1). We shall prove this formally, without making reference to the triangle. First:

Lemma 1: (n-1, k-1) + (n-1, k) = (n, k)

Proof: (n-1)!/((k-1)!((n-1)-(k-1))!) + (n-1)!/(k!((n-1)-k))!)
= (n-1)!/((k-1)!(n-k)!) + (n-1)!/(k!(n-k-1)!)
= k(n-1)!/(k!(n-k)!) + (n-k)(n-1)!/(k!(n-k)!)
= (k+n-k)(n-1)!/(k!(n-k)!)
= n(n-1)!/(k!(n-k)!)
n!/(k!(n-k)!)
(n, k)

Lemma 2: [k=0, n]∑(n, k) = 2^n

Proof: clearly this holds for n=0, since [k=0, 0]∑(0, k) = (0, 0) = 0!/(0!0!) = 1 = 2^0. Now, suppose it holds for some n. Then for n+1:

[k=0, n+1]∑(n+1, k)

Break off the first and last terms:

(n+1, 0) + [k=1, n]∑(n+1, k) + (n+1, n+1)

Of course, (n+1, 0) and (n+1, n+1) are both equal to 1, so:

2 + [k=1, n]∑(n+1, k)

Using lemma 1:

2 + [k=1, n]∑((n, k-1) + (n, k))

Breaking this up into two sums:

2 + [k=1, n]∑(n, k-1) + [k=1, n]∑(n, k)

Changing the indices of summation:

2 + [k=0, n-1]∑(n, k) + [k=1, n]∑(n, k)

Of course, 1=(n, n) and 1=(n, 0), so:

(n, n) + [k=0, n-1]∑(n, k) + [k=1, n]∑(n, k) + (n, 0)

Moving these into the sums:

[k=0, n]∑(n, k) + [k=0, n]∑(n, k)

Simplifying using the inductive hypothesis:

2^n + 2^n

And finally:

2^(n+1)

So if the hypothesis holds for some n, then it holds for n+1. We already know it holds for 0, so by induction, it holds for all n.

Finally, the main theorem:

for all even natural numbers n, [k=0, n/2]∑(n, 2k)

Obviously, this expression only makes sense where n is even, although if we adopt the convention that [k=0, n/2]∑(n, 2k) = [k=0, floor(n/2)]∑(n, 2k), then this actually holds for all natural numbers. In any case, we proceed as follows:

[k=0, n/2]∑(n, 2k)

First, break off the first and last terms:

(n, 0) + [k=1, n/2 - 1]∑(n, 2k) + (n, n)

Both (n, 0) and (n, n) are equal to 1:

2 + [k=1, n/2 - 1]∑(n, 2k)

Using lemma 1:

2 + [k=1, n/2 - 1]∑((n-1, 2k-1) + (n-1, 2k))

Expanding this series yields the terms ((n-1, 1) + (n-1, 2)) + ((n-1, 3) + (n-1, 4))... ((n-1, n-3) + (n-1, n-2)). This is clearly equal to:

2 + [k=1, n-2]∑(n-1, k)

Of course, 1=(n-1, 0) and 1=(n-1, n-1), so this is:

(n-1, 0) + [k=1, n-2]∑(n-1, k) + (n-1, n-1)

Moving those terms into the sum:

[k=0, n-1]∑(n-1, k)

Which by lemma 2 is:

2^(n-1)

Q.E.D.

Addendum: to show that the identity [k=0, floor(n/2)]∑(n, 2k) = 2^(n-1), we note that where n is even, this is nothing but [k=0, n/2]∑(n, 2k), which we already proved is equal to 2^(n-1). Where n is odd, [k=0, floor(n/2)]∑(n, 2k) = [k=0, (n-1)/2]∑(n, 2k). Breaking off the first term (there's no need to break off the last, since the resulting expression from the last term will be well-defined in this case):

(n, 0) + [k=1, (n-1)/2]∑(n, 2k)

Now, using lemma 1:

(n, 0) + [k=1, (n-1)/2]∑((n-1, 2k-1) + (n-1, 2k))

Which is nothing but:

(n, 0) + [k=1, n-1]∑(n-1, k)

And (n, 0) = 1 = (n-1, 0), so this is:

[k=0, n-1]∑(n-1, k)

Which is also 2^(n-1) by lemma 2.

Answer 2

You a minimum of ought to state the subject wisely. If n = 3, then a_n = 2 yet floor(sqrt(2n) + a million/2) = 3. So it is fake that a_n = floor(sqrt(2n)+a million/2). in case you meant that a_1 + a_2 + ... + a_n = floor(sqrt(2n)+a million/2), that still is fake: if n = 2, then a_1 + a_2 = 3 yet floor(sqrt(2n)+a million/2) = 2.