Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

travelers's blog

Formula??
By travelers, history, 10 years ago, In English

Can we devise a formula for a series like this,

S=n+7(n-1+7(n-2+7(n-3+.........)))

when n=1 S=1 first three terms are 1,9,66 someone says it has a formula but i cant find any help!!!

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://www.wolframalpha.com/input/?i=sum(7%5Ei+*+(n+-+i)+for+i+%3D+0...n)

→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

S(n + 1) = n + 1 + 7·S(n)

Now this can be solved by standart methods.

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I can offer to read about generating function (Link). In short:

S(0) = 0
S(n) = n + 7*S(n — 1)

Multiply first line by x^0, ans second by x^n and sum all lines. Assume S(0)*x^0 + S(1)*x^1+.... = G(x):
G(x) = 7xG(x) + (1 * x^1 + 2 * x^2 + 3 * x^3 + ....)
Expression in brackets can be simplify to x/(1-x)^2. So we can find formula:
G(x) = x/((1-x)^2*(1-7x)) = (7/(1 — 7x) — 1/(1 — x) — 6/(1-x)^2)/36. And we can expand all fractions:
1/(1 — ax) = (ax)^0 + (ax)^1 + ...;
1/(1 — x)^2 = (1 * x^0 + 2 * x^1 + 3 * x^2 + ...);

Calculate all coeffs in left part and all coeffs in right part. And we get finally formula:
S(n) = (7^(n + 1) — 7 — 6n)/36. Check formula for first n:

S(0) = 0;
S(1) = 1;
S(2) = 9;
S(3) = 66;

→ Reply