Thread: Discrete math hw

Originally Posted by entropic.color

This is my hw for this week, with which I am having much trouble with:

http://kodiak.ucsd.edu/alon/cse20/homework/hw5.pdf

mostly, I need help with #3 and #4.

For #3, I proved the basis, and am trying to solve the inductive step:

P(n) + (n+1_step) = P(n+1)

[ (2(1)+1)/(1+2+3) + ... + [(2n+1)/n(n+1)(n+1)] + [(2^(n+1)+1)/(n+1)(n+2)(n+3)] = (n+1)(5(n+1)+7)/4(n+2)(n+3)

and I'm trying to solve, but keep getting very complicated equations that i can't solve.

-------------------------

For #4, I (think I) figured out the formula, (or something like it, because it only works for n>=1), which is number_of_circles_after_nth_generation = [1+4(3^0 + 3^1 + ... + 3^n)]. I'm trying to prove the inductive step:

P(n) + step = P(n+1)
(1+4(3^0 + ... + 3^n [+3^(n+1)]) = (2^((n+1)+1)) - 4(n+1) - 3

and I keep backing myself into a corner with solving it ( I'm getting really complicated equations that I know are wrong because he doesn't expect us to know how to solve cubic equations, etc).

Thank you for helping!

I'll help you get started on #3:

You've already showed that this is true when n=1.

We now need to assume that this is true for n=k

This means that

Now we have to show that its true for n=k+1:

This means that we need to show that

But

Thus, we now see that

However, we already know that .

Therefore we now have to show that

Can you try to take it from here?

--Chris