Unrolling then solve for n=100

[scorpius1782]

Homework Statement

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

Homework Equations

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

[

 

[jbunniii]

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

 

[scorpius1782]

99, right?

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

 

[jbunniii]

99, right?

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

 

[scorpius1782]

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

 

[jbunniii]

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

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

 

[scorpius1782]

k-1?

 

[Ray Vickson]

k-1?

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.

 

[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.

 

[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)$?

 

[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.

 

[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?

 

[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.

 

[jbunniii]

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

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.

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

$$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$.

 

[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.

 

[jbunniii]

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.

Yes, that sounds right.

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.

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$.