Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider an array of numbers
$$ \color{#C00000}{1}\ \hphantom{7\ 6\ 5\ 4\ 7\ 3\ 5\ 7\ 2\ 7\ 5\ 3\ 7\ 4\ 5\ 6\ 7\ }\color{#C00000}{1}\\ 1\ \hphantom{7\ 6\ 5\ 4\ 7\ 3\ 5\ 7\ }\color{#C00000}{2}\ \hphantom{7\ 5\ 3\ 7\ 4\ 5\ 6\ 7\ }1\\ 1\ \hphantom{7\ 6\ 5\ 4\ 7\ }\color{#C00000}{3}\ \hphantom{5\ 7\ }2\ \hphantom{7\ 5\ }\color{#C00000}{3}\ \hphantom{7\ 4\ 5\ 6\ 7\ }1\\ 1\ \hphantom{7\ 6\ 5\ }\color{#C00000}{4}\ \hphantom{7\ }3\ \hphantom{5\ 7\ }2\ \hphantom{7\ 5\ }3\ \hphantom{7\ }\color{#C00000}{4}\ \hphantom{5\ 6\ 7\ }1\\ 1\ \hphantom{7\ 6\ }\color{#C00000}{5}\ 4\ \hphantom{7\ }3\ \color{#C00000}{5}\ \hphantom{7\ }2\ \hphantom{7\ }\color{#C00000}{5}\ 3\ \hphantom{7\ }4\ \color{#C00000}{5}\ \hphantom{6\ 7\ }1\\ 1\ \hphantom{7\ }\color{#C00000}{6}\ 5\ 4\ \hphantom{7\ }3\ 5\ \hphantom{7\ }2\ \hphantom{7\ }5\ 3\ \hphantom{7\ }4\ 5\ \color{#C00000}{6}\ \hphantom{7\ }1\\ 1\ \color{#C00000}{7}\ 6\ 5\ 4\ \color{#C00000}{7}\ 3\ 5\ \color{#C00000}{7}\ 2\ \color{#C00000}{7}\ 5\ 3\ \color{#C00000}{7}\ 4\ 5\ 6\ \color{#C00000}{7}\ 1\\ $$ The pattern: starting from 1 1, every consecutive natural number n will be inserted between two numbers beside each other whose sum equals n (2 between 1 1, 3 between 1 2, 4 between 1 3, etc )
You can see this pattern displayed above.
My question is: what is a(n) - the number of times we will have to write n in the nth row ?

My attempt: trying to find recursive formula between a(n) and a(n+1), but this seems hard.

share|improve this question
1  
$a(n)=$number of times you'll have to write $n$, where? The question is abit ambiguous. An illustration will be helpful. –  user21436 Feb 5 '12 at 9:51
1  
Oh sorry i fixed the ambiguity. –  Lorenz Chaos Feb 5 '12 at 10:10
    
Huh, but isn't it simple: $$a(n)=\begin{cases}1, ~~ n \neq 2\\2~~ \text{otherwise} \end{cases}$$ –  user21436 Feb 5 '12 at 10:13
1  
Holy Cow, I am sorry. –  user21436 Feb 5 '12 at 10:17
1  
I modified your array in an attempt to make it clearer. Feel free to revert if you don't like it. –  robjohn Feb 27 '13 at 16:52
show 1 more comment

2 Answers 2

up vote 8 down vote accepted

Your initial sequence of numbers consists in the denominators of the very well studied Farey sequence.

For $n\ge 2$ we have : "the number of elements of $F_n$ having denominator $n$ is equal to $\phi(n)$" : the Euler phi function.

A fascinating introduction to Farey sequences with the link to Ford circles may be found in Burger's excellent book 'Exploring the number jungle'.

share|improve this answer
    
In order to prove each row mentioned is denominators of Farey sequence, i must prove that the fractions add to F(n) is mediant of two consecutive elements in it, using the theorems of that book. From then i can deduce the answer of $\phi(n)$. However i'm having trouble with theorem 2.8 and 2.10 (2.7 is direct consequence of 2.5 and 2.6) –  Lorenz Chaos Feb 8 '12 at 16:57
add comment

This was too long for a comment so...

Theorem 2.8 : if $\frac pq\lt\frac rs$ are two consecutive fractions of $F_n\ $ then $ps-rq=-1$

Let's use the hint provided in the book : "Prove this theorem by induction on $N$. Assume the statement holds for $N=n$ and consider a rational number $a/b \in [0,1]$ with $b\gt n$. Show that $a/b$ must reside between two consecutive elements of $F_n$. What is the smallest $b$ could possibly be?"

At this point you should admit that $\frac pq\lt\frac ab\lt\frac rs$ with $\frac pq$ and $\frac rs$ consecutive fractions of $ F_n$ so that, from Lemma 2.6, $a=\lambda p+\mu r$ and $b=\lambda q+\mu s$ with $\lambda$ and $\mu$ positive integers (for zero we would have $\frac pq=\frac ab$ or $\frac ab=\frac rs$!). In conclusion the smallest possible value of $b$ is $q+s$, further we have $q+s\gt n\ $ because else the fraction $\frac{p+r}{q+s}$ would have been inserted earlier!
The only 'free docks' for $b=n+1$ are those for which $q+s=n+1$ (the sum of two consecutive denominators of $F_n$ is $n+1$ or more).
I hope that these indications will help you to prove 2.8 as well as 2.10.

I think that the Euler $\phi\ $ result is straightforward in Farey sequences : when you have to consider a new denominator $n\ $ (appearing in $F_n\ $) then you have only to insert the fractions $\frac an\ $ such that $(a,n)=1\ $ (and that's what $\phi\ $ counts!) because else the fraction simplifies and appeared earlier...

share|improve this answer
    
oh i see. Thank you. This book is very interesting. Maybe i will buy it :D –  Lorenz Chaos Feb 9 '12 at 4:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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