Two positive coprime natural integers $n,m$ and $0$ are given. at each step we can add the average of two given numbers to the set, if they are both odd or both even. Prove that this way you can generate all integers from $0$ to $n$.
I want to prove this by induction on n.
Base case: $n = 1$: You can divide $m$ by 2 at each step by adding the average of $m$ and 0 if it's even, or the average $m$ and 1 if it's odd. You can eventually generate 1.
Now i'm not sure how to prove the problem for $n=k+1$ using $n=k$. Any ideas?
Let the numbers ultimately produced be $0=a_0<a_1<\ldots< a_k$. Then for $1\le i\le k$, the difference $a_i-a_{i-1}$ is odd as otherwise we can additionally produce $\frac{a_i+a_{i-1}}2$ between $a_{i-1}$ and $a_i$. Therefore, $a_{i+1}-a_{i-1}$ is even for $1\le i<k$ and as $\frac{a_{i+1}+a_{i-1}}2$ cannot be a new number, we conclude $\frac{a_{i+1}+a_{i-1}}2=a_i$. In other words, our sequence is an arithmetic progression $a_i=id$ with some odd step size $d$. As $m,n$ are among the $a_i$, both must be multiples of $d$. Hence if we are given that $\gcd(n,m)=1$ (or more generally if $\gcd(n,m)$ is a power of $2$), we must have $d=1$ and thereby the desired result.