im asked to find the number of arithmetic sequences of d=1 (or consecutive sequences the way the question describes it), of length of at least 2 from the numbers {1,2,...,n}. the question adds that it needs to be done by proving via bijection that this number is equal to the cardinality of a certain set.
the way i approached the question is: for sequences of length 2 i could start with one sequence 1,2 and slide across till it reaches n-1, so for every sequence of length x there will be n-x+1 sequences and then we sum for all values of x from 2 to n.
but this clearly isnt a bijection, the only bijection i could think of is a function that sends each x from 1 to n to the subgroup of seuneces of length x (represented as x-long vectors). but after that i get stuck, can someone guide me?
(i learn this course in a different language so excuse my mistakes)
Let $S$ and $B$ be defined as $$ S=\{1,2,\dots,n\} \hspace{2cm} B=\{(a,b)|a,b\in S, a<b\}$$ Then the set $A$, of all arithmetic sequences with common difference $d=1$ and elements from $S$, is in bijection with the set $B$: $$(x,x+1,x+2,\dots, y)\in A\longleftrightarrow (x,y)\in B$$ Therefore $|A|=|B|$, and the cardinality of $B$ can be immediately calculated:
$$|B|=\left|\{(1,m),m=2,\dots,n \}\right|+\left|\{(2,m),m=3,\dots,n \}\right|+\dots $$ $$\implies |B|=(n-1)+(n-2)+\dots+1=\frac{n(n-1)}{2} $$