4
$\begingroup$

Hi, I have a triangle starting from $0$ and going up by one on the bottom row until there are $r$ items on the bottom row and there are $r$ rows a number is formed by adding the two numbers towards the fat end of the triangle together.

Example: $$x \downarrow\ $$ $$ \begin{matrix}12\end{matrix}\\ \begin{matrix}4 & 8\end{matrix}\\ \begin{matrix}1 & 3 & 5\end{matrix}\\ \begin{matrix}0 & 1 & 2 & \boxed{3}\end{matrix} $$ $$\begin{matrix}& & r - 1 \uparrow\end{matrix}$$ $\therefore$ when $r = 4$, $x = 12$.


When $r = 8$ $$ \begin{matrix}0\ \ & 1\ \ & 2\ \ & 3\ \ & 4\ \ & 5\ \ & 6\ \ & 7\ \ \end{matrix}\\ \begin{matrix}1\ \ & 3\ \ & 5\ \ & 7\ \ & 9\ \ & 11\ & 13\ \end{matrix}\\ \begin{matrix}4\ \ & 8\ \ & 12\ & 16\ & 20\ & 24\ \end{matrix}\\ \begin{matrix}12\ & 20\ & 28\ & 36\ & 44\ \end{matrix}\\ \begin{matrix}32\ & 48\ & 64\ & 80\ \end{matrix}\\ \begin{matrix}80\ & 112 & 144 \end{matrix}\\ \begin{matrix}192 & 256 \end{matrix}\\ \begin{matrix}448\end{matrix}\\ $$ $\therefore x = 448$

How do I work out $x$ from $r$? What is the formula? Any help by suggesting a new viewpoint or formula(e) would be greatly appreciated. Thank you.

$\endgroup$
3
$\begingroup$

A recursive solution: number the rows $0$ to $r-1$ with $0$ being the fattest, notice that the difference between consecutive numbers in row $k$ is $2^k$.

Denote by $f(n)$ the number in the last row of a triangle with $n$ rows. Then $f(n)=2f(n-1)+2^{n-2}$

Notice $f(1)=0,f(2)=1,f(3)=4$

From this recurrence we pass to $f(n)=(n-1)2^{n-2}$


The proof is by induction. Suppose $f(n)=(n-1)2^{n-2}$

then $f(n+1)=(n-1)2^{n-1}+2^{n-1}=n(2^{n-1})$ as desired.

$\endgroup$
  • $\begingroup$ but when n = 4 f(n) = (4-1)2^4-1 = 3x2^3 = 3*8 = 24 $\endgroup$ – user181782 Jun 9 '14 at 16:43
  • $\begingroup$ oh, yes give me a second. $\endgroup$ – Jorge Fernández Hidalgo Jun 9 '14 at 16:45
  • $\begingroup$ i thoght it was 12 as r1 = 0,1,2,3 r2=1,3,4 r3=4,8 r4=12 $\endgroup$ – user181782 Jun 9 '14 at 16:48
  • $\begingroup$ The formula is $(n-1)2^{n-2}$ $\endgroup$ – Jorge Fernández Hidalgo Jun 9 '14 at 16:48
  • $\begingroup$ I had made a mistake, but this one is correct. $\endgroup$ – Jorge Fernández Hidalgo Jun 9 '14 at 16:50
0
$\begingroup$

Consider the first two 'columns'. Notice any patterns?

$$0 \space 1\\1 \space 3 \\4 \space 8\\ 12\space 20$$

What is the rule?

$$a_{i+1} = a_i + b_i$$ $$b_{i+1} = a_{i+1} + 2 (b_i - a_i) = 3b_i - a_i$$

Try find a formula for $a_n$.

$\endgroup$
  • $\begingroup$ what is the Ai and Bi - what does it mean $\endgroup$ – user181782 Jun 9 '14 at 16:36
  • $\begingroup$ Sorry, $a_i$ refers to the first entry of the $i^{th}$ column and $b_i$ the second entry. By column, I mean reading the two diagonal columns of the triangle $\endgroup$ – muzzlator Jun 9 '14 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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