Question

How many arithmetic progressions of length 9 are there, such that the terms are integers from 1 to 70?

Answer 1

Since the arithmetic progression has 9 terms, let the first term be \(a\) and the last term be \(a+8d\), where \(d\) is the common difference.
Thus, your question is equivalent to finding the number of non-negative integer solutions to \(a+8d=k\) where k goes from 9 to 70.

Answer 2

Correction: The answer to your question is actually double the answer of my equivalent question, since we also need to consider negative values of \(d\).

Answer 3

OK, so the arithmetic progression has 9 terms, like a_1, a_2, a_3, ... , a_9
And the difference between each pair of terms is fixed, the same number
Right? @thongkun

Answer 4

How many arithmetic progressions of length 9 are there, such that the terms are integers from 1 to 70?

Details and assumptions
An Arithmetic Progression is a sequence of terms such that the difference between the consecutive terms is a constant. (1,2,3,4),(1,1,1,1),(4,3,2,1) are all valid arithmetic progressions of length 4.

Answer 5

The best I could come up with is a recursive formula.
Let \(b_k\) be the number of non-negative solutions to \(a+8d=k\).
We can prove that the generating function of \(b_k\) is \[B(x)=\frac{x}{1-x} \cdot \frac{1}{1-x^8}\] by considering the series expansion of \(B(x)\):
\[B(x)=(x+x^2+x^3+\dots)(1+x^8+x^{16}+\dots).\]
The exponent of \(x^k\) in this expansion is of the form \(c_1+8c_2\).

Answer 6

Also, every term a_i must be an integer
Also, a_1 = 1 and a_9 = 70
Now a_2 = a_1 + d, a_3 = a_2 +d, ... , a_9 = a_8 + d
where d is some integer number
Now, it follows from here that a_9 = a_1 + 8 *d
Because you add d 8 times to go from a_1 to a_9
Now, d = (a_9 - a_1)/8
d = 69/8 = 8.625
and d is not an integer
so, for example, a_2 = 9.625 is not an integer !
So, a_2 does not satisfy the condition of the problem
It seems like there are no such progressions, so that it has 9 terms, from 1 to 70, and all of them integers

Answer 7

Well, maybe they meant that a_1 > 1 and a_9 < 70 ?
Not equal to 1 and 70, but all 9 terms lie within interval 1 to 70 ?

Answer 8

Silly me, I immediately assumed that it's just as @ⒶArchie☁✪ last said.

Answer 9

I am not quite sure, it may be that they mean the second case, then we can try to count all possible progressions. tHe formulation is not exactly clear (the formulation of initial problem)
So, if a_1 =1 and a_9 = 70, then there are no such progressions, but in the second case, surely there are some
And we can count them

Answer 10

For example, one will be a_1 = 1, a_2 = 2, a_3 = 3, a_4 = 4 , ... , a_9 = 9
we can count first by going through all values of d
d must be integer from 1 to 8 !
Right ? d cannot be larger than 8.625 that we just obtained
Because, if d > 8.625 then all 9 terms will not fit into the interval from 1 to 70
because 8 * d < 70 -1
8 * d < 69 right ?

Answer 11

Ok, whatever a_1 is, it is always true that a_9 - a_1 = 8 * d
Do you agree ? @blockcolder

Answer 12

This is from the definition of arithmetic progression

Answer 13

a_1 is the first term, a_1 + d is the second term, ..., a_9 = a_1 + 8d is the 9th term

Answer 14

Yeah, but a_1 can be anything from 1 to 70, and d can be anything from -8 to 8. Moreover, some combinations of a_1 and d are incompatible due to the restriction that the terms be all between 1 and 70. How do you plan to count them?

Answer 15

How do you plan to count them? (y) :)

Answer 16

@blockcolder I have this plan. Every progression is uniquely defined by a_1 and d. So, we go through all possible d and a_1 and count them all. First, we start with d's, and I thought that negative ds are not considered But if you want, we can consider negative d as well
Then, we have 8 possible choices for positive d, d =1, d =2, d = 3, ... , d =8

Answer 17

@thongkun

Answer 18

Well, the negative d is for sequences like 9,8,7,...,1.

Answer 19

Now for every choice of d we will count all possible choices of a_1
For example, if d =1, then a_1 can be any integer from 1 to 62
Because if a_1 > 62, then a_9 will be larger than 62 + 8 = 70
So, a_9 will be larger than 70, and will not satisfy conditions of the problem
But any a_1 from 1 to 62 is OK,
So, we have 62 possible choices for a_1 and 61 possible sequences with d =1
Those are unique progressions, and we count them all
Then, we go to d =2 ... and d =3 .. and finally d = 8
This is my plan

Answer 20

I think the answer to this problem dosent acquire negative d

Answer 21

@thongkun @blockcolder What do you think on this plan?

Answer 22

also @blockcolder Right ... we will deal with negative d as well later

Answer 23

The number of progressions with negative d is just equal to number of progressions with positive d
Did you consider negative d in class ?
Or only positive d, when you were discussing arithmetic progressions ? @thongkun

Answer 24

wait me for understand your plan. It seems good. :)

Answer 25

Even, if we add negative d, the number of progressions will be just double ... it is easy to take them into account

Answer 26

That's actually a nice idea. It's better than my generating functions at least. Here's a medal for you. :)

Answer 27

Thank you! o.o

Answer 28

I am glad you guys understand the plan and agree on it

Answer 29

There might be other ways to solve this problem ... I just think of this plan at the moment, it is the first idea that came to my mind
So, let us start counting

Answer 30

I think d =0 is acceptable in the problem.

Answer 31

If d =0, then all terms are the same
OK, then the number of progressions with d = 0 is 70

Answer 32

Because this is just the number of integers from 1 to 70

Answer 33

If you want to count those single numbered progressions with d = 0 then it is just 70