0
$\begingroup$

I need to prove this formula that calculate $[n/x^i]$ for $n,x$ positive integers, and $ i>=0$ integer.

$[n/x^{i+1}]$ = $[[n/x^i]/x]$

I know I need to use division with remainder when $n=[n/x^i]x^i+r_i$ for $0<=r_i and $[n/x^i]=[[n/x^i]/x]$ for $0<=r

I really tried to play with this but I got nothing...

1 Answers 1

1

Suppose $k=[n/x^{i+1}]$ and $h=[n/x^i]$. So your statement is equivalent to prove that $[h/x]=k\ \ \ \text{ that is } \ \ \ kx\leq h<(k+1)x .$ Now, by definition of $[-/-]$ we have that

(1) $kx^{i+1}\leq n<(k+1)x^{i+1}$;

(2) $hx^{i}\leq n<(h+1)x^{i}$.

In order to verify that $kx\leq h$, it is enough to apply (1) and (2), in fact $kx^{i+1}\leq n<(h+1)x^{i}$ says us that $kx, that is, $kx\leq h$. Similarly, the fact that $hx^i\leq n<(k+1)x^{i+1}$ tells us that $h<(k+1)x$.