Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

migrated from stackoverflow.com Oct 20 '13 at 22:27

This question came from our site for professional and enthusiast programmers.

    
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 –  U2744 SNOWFLAKE Oct 20 '13 at 22:26

2 Answers 2

up vote 0 down vote accepted

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!

share|improve this answer
    
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

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.