0

This is probably simple (if not, my apologies beforehand), but I have the following formula:

$$f(0) = 2$$ $$f(x) = 6x + 2 + f(x -1) \; \text{ where } x \in \mathbb{N}_{\gt 0}$$

The formula actually represents a quadratic performance in a certain algorithm, but the fact that it is quadratic is not immediately clear.

I was considering that the sum of natural numbers can be expressed as $$\sum_{k=1}^n k= \frac{n(n+1)}{2}$$, which makes the quadratic factor apparent. I figured it shouldn't be too hard to express the above recursive function similarly in a non-recursive way, showing or proofing that it is indeed quadratic.

I'd be interested in how to deduce the steps to get to the formula, instead of only getting the (right) answer.

Note: the series expressed here is: $2, 10, 24, 44, 70, 102, 140....$

Abel
  • 219

1 Answers1

3

$$f(0)=6(0)+2$$

$$f(1)-f(0)=6(1)+2$$

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

$$\vdots$$

$$f(x)-f(x-1)=6(x)+2$$

Adding all these equations,

$$\begin{align}f(x)&=\sum_{i=0}^x (6x+2)\\&=\left(\sum_{i=1}^x6x\right)+2(x+1)\\&=3x(x+1)+2(x+1)\\&=(x+1)(3x+2)\end{align}$$

Guy
  • 8,857
  • 1
  • 28
  • 57
  • What you are actually doing is finding the individual elements that need to summed, as in $f(x) = (6(0) + 2) + (6(1) + 2) + (6(2) + 2) + (6(3) + 2) + .... + (6(x) + 2)$ which shows the expression for the $\sum_{}$-formula. I am, however, a bit unclear about the first sum-deduction step, from $(6x + 2)$ to $2(x + 1)$. I can see that it is correct, but what rule or law is applicable for that deduction? How do I get there? – Abel Apr 01 '14 at 14:02
  • 1
    @Abel I am splitting $\sum (6x+2)$ into $\sum 6x$ and $\sum 2$ – Guy Apr 01 '14 at 14:05
  • Do you see why we can do that? – Guy Apr 01 '14 at 14:06
  • Thanks, yes I see it now. Apparently $\sum_{i=0}^{n}{2}$ means the sum of $n + 1$ two's (as in $2 + 2 + 2 ...$), and it easily follows from the sequence: adding 2 appears in every element in your deduction series. From there it is easy to deduce $2(x + 1)$, clear as rain now ;). – Abel Apr 01 '14 at 14:14
  • @Abel good to hear. – Guy Apr 01 '14 at 14:17
  • In addition, it makes sense, considering it is about sums, that any $\sum{x + y}$ is equal to $\sum{x} + \sum{y}$. I just rarely work with sums and products, let alone that I can remember rules I have learned long ago in college. Thanks for you clear answer. – Abel Apr 01 '14 at 14:17
  • @Abel you're welcome. Yes that rule is valid. In general, just try shuffling around the terms, you can rearrange. Except, if you are working with infinite sums, you have to be careful. – Guy Apr 01 '14 at 14:25