0

f(1)=1, and f(n) = f(n-1)+2(n-1)

Using substitution, here are the first few steps: f(n-1) = f((n-1)-1) + 2((n-1)-1)

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

And then eventually I see that f(n+(-1)*2^j) = f(n+(-1)*2^(j+1)) + 2n + 2(-1)*2^(j+1), where j is an increasing integer >=1

What do I do now? It looks like 2(-1)*2^(j+1) will diverge to negative infinity...

The answer is f(n) = (n-1)n + 1 (using wolfram) but i have no idea what they did..

Brian M. Scott
  • 616,228
Gary Choi
  • 167
  • I never learned the "triangle number formula" and I'm supposed to use substitution, but thanks for pointing me to the math section. I hope I get more responses there, though this was part of a compsci assignment. – Gary Choi Oct 20 '13 at 22:25
  • Don’t repost, I’ll move it – Ry- Oct 20 '13 at 22:26

2 Answers2

1

Here’s the substitution reduction:

$$\begin{align*} f(n)&=f(n-1)+2(n-1)\\ &=f(n-2)+2(n-2)+2(n-1)\\ &=f(n-3)+2(n-3)+2(n-2)+2(n-1)\\ &\;\vdots\\ &=f(n-k)+2(n-k)+2\big(n-(k-1)\big)+\ldots+2(n-2)+2(n-1)\\ &\;\vdots\\ &=f(1)+2\big(n-(n-1)\big)+2\big(n-(n-2)\big)+\ldots+2(n-2)+2(n-1)\\ &=1+\sum_{k=1}^{n-1}2k\\ &=1+2\sum_{k=1}^{n-1}k\\ &\overset{*}=1+2\left(\frac{n(n-1)}2\right)\\ &=1+n(n-1)\\ &=n^2-n+1\;. \end{align*}$$

The formula for the sum of the first $n$ positive integers that I used at the starred step is a common special case of the more general formula for the sum of a finite arithmetic progression, one that’s worth knowing in its own right.

Brian M. Scott
  • 616,228
  • Thank you! I didn't do the second step correctly T_T – Gary Choi Oct 20 '13 at 22:44
  • @Gary: You’re welcome! (It sometimes helps to write out a few lines using a specific value of $n$, like $n=5$; the pattern may not be quite so apparent, but you’re also less likely to make purely symbolic errors.) – Brian M. Scott Oct 20 '13 at 22:47
  • @minitech: I fixed everything. $\sum_{k=1}^nk$ is $\binom{n+1}2$, not $\binom{n}2$, so $\sum_{k=1}^{n-1}=\binom{n}2=\frac{n(n-1)}2$. – Brian M. Scott Oct 20 '13 at 22:51
0

This is how it expands:

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

And you can see that we’ll get to $f(1) = 1$ eventually, and that will be when $n - a = 1$. So what this is actually saying is:

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

i.e.

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

So one plus twice the sum of $1$ to $n - 1$ inclusive, which is one plus twice the $n-1$th triangle number. The nth triangle number is $\dfrac{n^2 + n}2$, so the whole thing is:

$$1 + 2\left(\dfrac{(n-1)^2+(n-1)}{2}\right)$$ $$1 + (n - 1)^2 + n - 1$$ $$(n - 1)^2 + n$$ $$n^2 - 2n + 1 + n$$ $$n^2 + 1 - n$$ $$(n - 1)n + 1$$

… which is indeed what Wolfram got you!

Ry-
  • 181
  • Oh! The problem was I wasn't directly substituting back the left hand side of the equation (second step) as f(n) (instead continuing as f(n-1) which made it hard to see the pattern. Thanks! – Gary Choi Oct 20 '13 at 22:42