Problem of the week #15 - July 9th, 2012

[Jameson]

Thank you to grgrsanjay for this idea.

Given the sequence where \(\displaystyle a_1=7\), \(\displaystyle a_2=77\), \(\displaystyle a_3=777\) and so on, derive a formula for summing the first n terms of the sequence.

Bonus: Prove through induction that this formula is valid.

Remember to read the POTW submission guidelines to find out how to submit your answers!

 

[Jameson]

Congratulations to the following members for their correct solutions:

1) soroban (derivation of formula)
2) BAdhi (derivation of formula)
3) Reckoner (derivation of formula and proof by induction)
4) Sudharaka (derivation of formula and proof by induction)
5) veronica1999 (proof by induction)

Honorable mention goes to sbhatnagar who was completely correct until the very last line of the solution, but made a small error in the final answer.

Solution:

Derivation of formula (from soroban)

Spoiler

[tex]S_n \;=\;7 + 77 + 777 + 777 + \cdots + \underbrace{777\cdots7}_{n\:7's}[/tex]

. . . [tex]=\;7\big(1 + 11 + 111 + 1111 + \cdots + \underbrace{111\cdots1}_{n\:1's}\big)[/tex]

. . . [tex]=\;7\left(\frac{10-1}{9} + \frac{10^2-1}{9} + \frac{10^3-1}{9} + \frac{10^4-1}{9} + \cdots + \frac{10^n-1}{9}\right) [/tex]

. . . [tex]=\;\tfrac{7}{9}\bigg[\underbrace{(10 + 10^2 + 10^3 + \cdots + 10^n)}_{\text{geometric series}} - \underbrace{(1 + 1 + 1 + \cdots + 1)}_{n\:1's}\bigg][/tex]

[tex]\text{The geometric series has the sum: }\:10\!\cdot\!\frac{10^n-1}{9}[/tex]


[tex]S_n \;=\;\tfrac{7}{9}\bigg[10\cdot\frac{10^n-1}{9} - n\bigg][/tex]

[tex]S_n \;=\;\tfrac{7}{81}\left(10^{n+1} - 9n - 10\right) [/tex]

Proof by induction (from Reckoner)

Spoiler

Proof, using induction: For \(n = 1\), the sum is simply the first term in the sequence, \(a_1 = 7\). The formula gives

\[\frac7{81}\left(10^2-9-10\right) = \frac7{81}\cdot81 = 7,\]

which proves the base case. Now, assume that the formula gives the correct sum when \(n = k\). If \(n = k+1\) we have

\[\sum_{i=1}^{k+1}a_i = a_{k+1} + \sum_{i=1}^ka_i\]

\[=\frac79\left(10^{k+1}-1\right) + \frac7{81}\left(10^{k+1}-9k-10\right)\]

\[=\frac7{81}\left(9\cdot10^{k+1} - 9\right) + \frac7{81}\left(10^{k+1} - 9k-10\right)\]

\[=\frac7{81}\left(10\cdot10^{k+1} - 9k - 9 - 10\right)\]

\[=\frac7{81}\left[10^{(k+1)+1} - 9(k + 1) - 10\right]\]

Therefore the formula is valid for all integers \(n\geq1\):