Am I meant to assume a_i is defined the same way as a_n for each of 1<= i <= n-1 ?
If so, I think I see the proof by induction on n, but the question just says a_i is defined for each 1<=i<=n-1, not that it is defined in that way. Is the question just overly vague or am I missing something obvious?
If only a_n is defined as the greatest integer such that the sum from 0 to n of each a_i/k^i is <=x, then I think there are counterexamples to the hypothesis, right?
Like if x=0.32, k=2, n=2, then a_0=0, and the inequality is satisfied by a_1 = 2 > k-1 = 1 and a_2 = -3 < 0.
Yes, another way to look at it is to reform the inequality as
if that makes it clearer?
Given this we know that a1 is the largest integer s.t. k*(x - a0) >= a1
(Why does a1 even exist might be a good question?)
Then show that a1 <= k-1 (just substitute in).
Assume that ai <= k-1 is proven for all integers i=1,…,n (where n might be 1) and show that an+1 <= k-1 is true as well.
Hope this helps? If not please do say so I have more hints but it’s a fine line between hinting and spoonfeeding and I have no feeling for your proficiency (there is nothing wrong with spoonfeeding when necessary so don’t be afraid to ask, but it’s obviously bad when it’s not necessary)
Yeah, that’s helpful. So I show that 0 <= a_1 <= k-1 from a_1 <= k(x - a_0) < a_1 + 1 by showing 0 <= (x - a_0) < 1 which implies 0 <= k(x - a_0) < k. That’s the base case. Then I assume that the hypothesis holds for some positive integer n-1. From there I manipulate the inequalities to show that they imply 0<= a_n <=k-1.
Then having already assumed 0 <= a_i <= k-1 for all 1 <= i <= n-1, that means it is the case for all 1<= i <= n. Since I have shown it to be true for n=1, it is true for n=2. Since it is true for n=1 and n=2, it is true for n=3, and so on for all positive integers n.
Is this the way? Also, I think this technique is an example of strong induction and not regular induction, is that right?
Oh just be clear
The hypothesis is “0 <= ai <= k-1 for all i <= n-1” right?
Yes, that one.
Yes and yes 😁 I would show both inequalities seperately, i.e. one chain of inequalities for 0 <= ai and another for ai <= k-1 (or < k) (in the base case as well) just for clarity but the argument is solid.👍