How can we find the summation of products which are functions of n in terms of n?

Question

Particularly I am talking about the answer in terms of n of following:
Sum from i=0 ... n-1 of the following:
(3^i) * (2^(n-i) * (n-i)

I went with the Pascal's solution, but before choosing you the best answer, let me ask you that. Did you also verify the end closed form solution by putting values?
Also this was a part of the calculation while I was solving the recurrence equation:
T(f) = 3T(f/2) + f log f
and got
Sum from i=0 ... n-1
(3^i) * (2^(n-i) * (n-i)
plus a 3^n
all that was while assuming n= log base 2 of f

Answer 1

Edit: Sorry about that -- if you read the first version of this, it contained several serious arithmetical errors. The current version should be correct, though.

Edit 2: Yes, I did numerically verify the closed-form solution, which was how I detected the arithmetical errors I mentioned in my first edit. As for your recurrence relation, if we define U(n) = T(2^n) (so that n=log₂ f), your recurrence relation becomes U(n) = 3U(n-1) + n 2^n, and it is easy to verify algebraically that the solution I gave you satisfies that recurrence relation as well. Note that you don't have to add 3^n to get a solution, although you can -- in fact, adding any multiple whatsoever of 3^n to a valid solution to the equation will yield another valid solution to the equation, since 3^n solves the homogeneous equation U(n) - 3U(n-1) = 0 (so for instance, -(n+3)*2^(n+1) also solves the recurrence relation).

Original post:

2*3^(n+1) - (n+3)*2^(n+1)

[k=0, n-1]∑(3^k * 2^(n-k) * (n-k))

The first thing to do is extract all the constants. This means get the 2^n outside:

2^n * [k=0, n-1]∑(3^k * 2^(-k) * (n-k))

We can now combine the bases:

2^n * [k=0, n-1]∑(3^k * (1/2)^k * (n-k))

2^n * [k=0, n-1]∑((3/2)^k * (n-k))

Now we can use the distributive property and linearity of summation to split this into two series. Since I've done problems like this many times before, I already know the trick I'm going to use, so I'll save myself a step by breaking this apart in a slightly unusual manner:

2^n * [k=0, n-1]∑((3/2)^k * ((n+1) - (k+1)))

2^n * [k=0, n-1]∑((3/2)^k * (n+1) - (3/2)^k * (k+1))

2^n * [k=0, n-1]∑((3/2)^k * (n+1)) - 2^n * [k=0, n-1]∑((3/2)^k * (k+1))

Now, we can extract the constant from the geometric series on the left:

2^n * (n+1) [k=0, n-1]∑(3/2)^k - 2^n * [k=0, n-1]∑((3/2)^k * (k+1))

And this can be summed using the well-known formula [k=0, n]∑r^k = (1-r^(n+1))/(1-r):

2^n * (n+1) (1 - (3/2)^n)/(1-3/2) - 2^n * [k=0, n-1]∑((3/2)^k * (k+1))

Simplifying:

2^n * (n+1) ((3/2)^n - 1)/(1/2) - 2^n * [k=0, n-1]∑((3/2)^k * (k+1))

2*2^n * (n+1) ((3/2)^n - 1) - 2^n * [k=0, n-1]∑((3/2)^k * (k+1))

2(n + 1)(3^n - 2^n) - 2^n * [k=0, n-1]∑((3/2)^k * (k+1))

Okay, now for the series on the right, we'll just temporarily replace the 3/2 with a variable x. So we have:

2(n + 1)(3^n - 2^n) - 2^n * [k=0, n-1]∑(x^k * (k+1)) @ x=3/2

Of course, now that the x is a variable, the term is immediately recognizable as a derivative (this is the trick I was talking about, and why I broke the sum apart in such an odd manner at the beginning). So we have:

2(n + 1)(3^n - 2^n) - 2^n * [k=0, n-1]∑(d/dx (x^(k+1))) @ x=3/2

Of course, the sum of a bunch of derivatives is the derivative of the sum, so the summation and derivation commute, and we have:

2(n + 1)(3^n - 2^n) - 2^n * d/dx [k=0, n-1]∑(x^(k+1)) @ x=3/2

And this is just a geometric series, and can be evaluated as such:

2(n + 1)(3^n - 2^n) - 2^n * d/dx ((x - x^(n+1))/(1-x)) @ x=3/2

And now that the summation is gone, we can simply take the derivative using the quotient rule:

2(n + 1)(3^n - 2^n) - 2^n * ((1 - (n+1) x^n) (1-x) + (x - x^(n+1)))/(1-x)² @ x=3/2

And now that we have a closed-form expression, we just re-evaluate it at 3/2:

2(n + 1)(3^n - 2^n) - 2^n * ((1 - (n+1) (3/2)^n) (1-(3/2)) + (3/2 - (3/2)^(n+1)))/(1-3/2)²

And simplify:

2(n + 1)(3^n - 2^n) - 2^n * ((1 - (n+1) (3/2)^n) (-1/2) + 3/2 - (3/2)^(n+1))/(-1/2)²

2(n + 1)(3^n - 2^n) - 2^(n+2) ((1 - (n+1) (3/2)^n) (-1/2) + (3/2 - (3/2)^(n+1)))

2(n + 1)(3^n - 2^n) - 2^(n+2) (1/2 (n+1) (3/2)^n - 1/2 + 3/2 - (3/2)^(n+1))

2(n + 1)(3^n - 2^n) - (2 (n+1) 3^n - 2^(n+1) + 3*2^(n+1) - 2 * 3^(n+1))

2(n + 1)(3^n - 2^n) - (2 (n+1) 3^n + 2^(n+2) - 2 * 3^(n+1))

2(n + 1)(3^n - 2^n) - (2 (n+1) 3^n + 2^(n+2) -6*3^n)

2(n + 1)(3^n - 2^n) - (2 (n-2) 3^n + 2^(n+2))

2(n + 1)(3^n - 2^n) - 2 (n-2) 3^n - 4*2^n

2(n + 1)*3^n - 2(n+1)*2^n - 2 (n-2) 3^n - 4*2^n

2(3)*3^n - 2(n+3)*2^n

2*3^(n+1) - (n+3)*2^(n+1)

Answer 2

Hmm...I'm uncertain about exactly how your random movement should work (as others have mentioned). For simplicity I'll discretize it and say that the bubble will make one of 7 choices: stay where it is, move left, right, up, down, back, or forward; all with equal probability. If this is the case, we can project the movements into a single axis, since we'll only be able to run into one wall, and each of our axes are indistinguishable from one another. So, focusing on say the x-axis, we have for each step, P(-1/n) = P(+1/n) = 1/7 P(0) = 5/7. In technical terms, we're looking at an application of homogeneous Markov chains, at least sort of. I haven't figured out quite how to make the solution fall out, but I think I should at least see if my discrete model is acceptable, or if you would rather see a properly constructed parameterized function such that the total derivative wrt time is 1/n. A couple of notes based on my intuition: I think that any simulation would certainly end in the destruction of the bubble; however, theoretically the bubble could live on forever. The real question is what is the probability remaining for such a situation (after subtracting all other probabilities of death). When I get home to my own computer I may put together a few simulations and/or excel formulas. EDIT (immediately after posting): holdm is right that Brownian motion is more accurate for what you want. If we want to get some sort of exact result though I think we'll need some sort of simplification.

Answer 3

there is no standard way, you just use different methods and skills
For your problem:
you can write the sum as:

n*2^n* sum (3/2)^i - 2^n* sum (3/2)^i * i

Now for sum (3/2)^i, you use the formula:
1+x+x^2+...+x^(n-1)= (1-x^n)/(1-x), taking x=3/2. (*)

the sum (3/2)^i* i is a bit more complicated

you can write as sum(3/2)^i *(i+1) - sum (3/2)^i

Now taking derivative in (*) relation you get:
1+2x+....+(n-1)x^(n-2) = ((1-x^n)/(1-x))'

you use this formula to find

sum(3/2)^i*(i-1) taking x=3/2