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!