Unrolling then solve for n=100

1. Mar 18, 2014

scorpius1782

1. The problem statement, all variables and given/known data
Can someone check that I'm doing this correctly? Someone else got another answer entirely but I don't see where my mistake could be...

$f(1)=2$
$f(n)=1+f(n-1)+n^2$

then solve for n=100

2. Relevant equations

3. The attempt at a solution
Unrolling:
$f(n)=1+f(n-1)+n^2$
$f(n)=1+1+f(n-2)+(n-1)^2+n^2$
$f(n)=1+1+1+f(n-3)+(n-2)^2+(n-1)^2+n^2$
so $k+f(n-k)+\sum_{i=0}^k(n-i)^2$

for n=100
$99+2+\sum_{i=0}^{99}(100-i)^2$
101+338350=338451

[

2. Mar 18, 2014

jbunniii

How many terms are there in the sum $\sum_{i=0}^{k}(n-i)^2$?

3. Mar 18, 2014

scorpius1782

99, right?

also, for got to write that $n\geq2$

4. Mar 18, 2014

jbunniii

For general $k$, how many terms are there in $\sum_{i=0}^{k}(n-i)^2$?

5. Mar 18, 2014

scorpius1782

Not sure I'm understanding, there is just the (n-i)^2 term in the summation.

6. Mar 18, 2014

jbunniii

How many things are you adding if you write $\sum_{i=0}^{k}$? Hint: the answer is not $k$.

7. Mar 18, 2014

scorpius1782

k-1?

8. Mar 18, 2014

Ray Vickson

Now you are just guessing. Don't do that. Work it out logically, or try a few small k values to see what you get.

9. Mar 18, 2014

scorpius1782

Okay. $\sum_{i=0}^3 i$=0+1+2+3, means 4 terms. so k+1

Edit:
i took k-1 from wiki. As for this I only have th option of k or k-1 since it is a multiple choice question. but the n=100 isn't.

10. Mar 18, 2014

jbunniii

So do you see why $k+f(n-k)+\sum_{i=0}^k(n-i)^2$ is not a correct expression for $f(n)$?

11. Mar 18, 2014

scorpius1782

No, not really. I think I know what the answer is, but I don't really see why what I have is wrong. It seems so straightforward.

12. Mar 18, 2014

jbunniii

Take a look at the previous line, which is correct:
$$f(n)=1+1+1+f(n-3)+(n-2)^2+(n-1)^2+n^2$$
How many "1" terms are you summing?
How many $(n-i)$ terms are you summing?

Now compare your general formula, which is incorrect:
$$f(n) = k+f(n-k)+\sum_{i=0}^k(n-i)^2$$
How many "1" terms are you summing?
How many $(n-i)$ terms are you summing?

13. Mar 18, 2014

scorpius1782

3 1's and 2 (n-1)'s.

then k 1's and k(n-i)'s.

So it should be summed from 0 to k-1, then.

14. Mar 18, 2014

jbunniii

I counted 3 (n-i)'s: $(n-2)^2 + (n-1)^2 + n^2$. So the number of $1$'s and the number of $(n-i)$'s should match.

$$f(n) = k+f(n-k)+\sum_{i=0}^k(n-i)^2$$
Well, there are $k$ 1's, but didn't we just agree that the summation $\sum_{i=0}^{k}$ is adding $k+1$ things? So you are summing $k+1$ of the $(n-i)^2$ terms when it should be $k$.

15. Mar 18, 2014

scorpius1782

Yeah, sorry I keep not counting $n^2$. So, I need to to go from 0 to k-1. Since, k is 1 more than the total number I need to sum.

The TA gave an answer that didn't make any sense to me. They got the summation of $f(n) = k+f(n-k)+\sum_{i=0}^k i^2$ but I don't see how that is correct at all.

16. Mar 18, 2014

jbunniii

Yes, that sounds right.

No, it's not correct. For example, plug in $k=1$. Then the TA's formula gives you $f(n) = 1 + f(n-1) + 1^2$ whereas the problem statement requires $f(n) = 1 + f(n-1) + n^2$.