Thread: Discrete math hw

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!

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 $\displaystyle \sum_{i=1}^k\frac{2i+1}{i(i+1)(i+2)}=\frac{k(5k+7) }{4(k+1)(k+2)}$

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

This means that we need to show that $\displaystyle \sum_{i=1}^{k+1}\frac{2i+1}{i(i+1)(i+2)}=\frac{(k+ 1)(5k+12)}{4(k+2)(k+3)}$

But $\displaystyle \sum_{i=1}^{k+1}\frac{2i+1}{i(i+1)(i+2)}=\sum_{i=1 }^k\frac{2i+1}{i(i+1)(i+2)}+\frac{2k+3}{(k+1)(k+2) (k+3)}$

Thus, we now see that $\displaystyle \sum_{i=1}^k\frac{2i+1}{i(i+1)(i+2)}+\frac{2k+3}{( k+1)(k+2)(k+3)}=\frac{(k+1)(5k+12)}{4(k+2)(k+3)}$

However, we already know that $\displaystyle \sum_{i=1}^k\frac{2i+1}{i(i+1)(i+2)}=\frac{k(5k+7) }{4(k+1)(k+2)}$.

Therefore we now have to show that $\displaystyle \frac{k(5k+7)}{4(k+1)(k+2)}+\frac{2k+3}{(k+1)(k+2) (k+3)}=\frac{(k+1)(5k+12)}{4(k+2)(k+3)}$

Can you try to take it from here?

--Chris