Reimbursement formula

Let’s assume that you work at an awesome company as a contractor.
They allow you to purchase equipment, and will reimburse the money you spent.

However, as a freelancer, you have to pay taxes. Let’s assume taxes are at 10% for any payment you receive on your account.

To further increase the greatness of the company, they say they will pay the taxes for you as long as you do the proper calculation.

So, as an example, let’s say you spend like $100 on computer equipment and ask for $100 reimbursement.
You will receive $100 on your bank account and have to pay 10% of that in taxes, so that’s $10, so you end up with $90.

You might also try to ask for $110 from the company, but 10% of that is $11 so you are left with $99. If you ask them to send you $11 for the taxes you paid, you will again have to pay 10% of $11 ($1.1) in taxes, and so on.

So the question is, how much money should the company reimburse you once, so that you get an amount close to the one you spent which includes taxes?

The answer is, if N is the money spent, you need to ask for reimbursement of $N + \lceil \frac{N}{9} \rceil$ money.

As an example:

I spend: $100
They send: $N + \lceil \frac{N}{9} \rceil$ , or $112
I pay tax: 10% * $112 = $11.2

Now, it holds that $\$112 = Send \geq Spend + Tax = \$111.2$

To derive that formula, we need to think in terms of recursion. Consider that multiple transactions are made, and for each transaction, you need to pay 10% in taxes of the transaction value.

Start with a number N:
1. Ask for pay of N money (company reimburses N)
2. Ask for pay of 10% of N (company reimburses 10% of N)
3. Ask for pay of 10% of 10% of N (company reimburses 10% of 10% of N)
…

And then, sum all the terms.

That makes something like: $S = N + N/10 + N/100 + ... = N(1 + 1/10 + 1/100 + ...)$ .

To calculate the $1 + 1/10 + 1/100 + ...$ part, we can let $n = 1.1111...$ . So, $10n = 11.1111...$ and $10n - n = 9n = 10$ and we get that $n = 10/9$ . We rewrite that as $1 + 1/9$ so that we can use ceil on the fractional part to get an integer.

P.S. I work at Automattic 🙂

Square of product of successive naturals

I’ve been working on an interesting task from a regional math contest:

Prove that the product of 8 successive naturals cannot be a natural number to the power of 4.

To prove this, we will first take a look at two other theorems (and prove them), and then use them to prove the original statement.

I. $\sqrt{x}$ irrational $\implies \sqrt{\sqrt{x}}$ irrational

To prove this, it suffices proving the contrapositive:
$\sqrt{\sqrt{x}}$ rational $\implies \sqrt{x}$ rational.

We have that for some a, b, $a/b = \sqrt{\sqrt{x}}$

Square both sides to get $a^2/b^2 = \sqrt{x}$ . Thus, $\sqrt{x}$ is rational.

II. $\sqrt{x(x+1)}$ is irrational

To prove this, note that x and (x+1) need to be squares. Consider for some a, $x = a^2$ . Further, for some b, $x + 1 = b^2$ .

Now, $b^2 - a^2 = (b - a)(b + a) = 1$ . But the only way this is possible if $b - a = 1/(b + a)$ .

Since a and b are positive naturals, we reach a contradiction for the identity above and thus either x or x+1 have no squares. In either case, $\sqrt{x(x+1)}$ is irrational.

III. Prove that there is no y s.t. $y^4 = x(x+1)(x+2)(x+3)(x+4)(x+5)(x+6)(x+7) = *$

We will assume that such y exists and reach a contradiction.

Rewrite as $y = \sqrt{\sqrt{*}}$ and suppose y is rational.

From I we have that it suffices to only prove that $\sqrt{*}$ is rational.

From II we have that either x or (x+1) is irrational. At least one of the 8 elements has no square, and we reach a contradiction. Thus y is irrational.

Life keywords

A few keywords for life that everybody should be doing on a regular basis. 🙂

Life. Family. Love. Health. Work. Improve/Grow. Socialize. (Keep) Try(ing). Patience. Belief. Balance. Food. Rest. Relax. Think.

If you can do most of these, you should be happy and consider yourself lucky.

Consecutive odd primed integers

A few years ago, for some reason (I don’t remember exactly what it was) I thought of the following problem and tackled around a solution for it:

Prove that the triplet $(3, 5, 7)$ is the only triplet of consecutive odd integers such that all integers in it are primes.

In other words, prove that $\exists! n \in N (2n + 1, 2n + 3, 2n + 5)$ are primes.

We already know if we set $n = 1$ that we get the triplet $(3, 5, 7)$ , but as for the part of proving that this is unique, we need to show that at least one member of the triplet is divisible by 3. So, for example, for $n = 3$ we have $(7, 9, 11)$ , and 9 is not a prime because it’s divisible by 3.

We can use induction on n. The base case is already there for $n = 1$ , so for the inductive step we can assume that either of the members is divisible by 3 (but not the remaining). Now assuming one of the members in $(2n + 1, 2n + 3, 2n + 5)$ is divisible by 3, we need to show that one of the members in $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.

From here, we have 3 cases:

$2n + 1$ is divisible by 3. Then, so is $2n + 4$ , and $2n + 7$ , thus one of $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.
$2n + 3$ is divisible by 3. Thus one of $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.
$2n + 5$ is divisible by 3. Thus one of $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.

So, since at least one member of $(2n + 1, 2n + 3, 2n + 5)$ is divisible by 3, but only 3 is a prime (and not multiples of 3 of course), we get that $(3, 5, 7)$ is the only triplet of consecutive odd integers such that all members are prime.

Proof of the binomial theorem

While working on How To Prove It, I found this in the exercises.
To me, the binomial formula is really trivial, but it’s an interesting thing to prove because it requires manipulating summations and some algebra tricks. So let’s get started.

Prove that for all real number x and y, and every natural n:
$(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k} y^k$
We will use mathematical induction on n.

Base case:
$n = 0: (x+y)^0 = 1 = {0 \choose 0} x^0 y^0$

Inductive hypothesis:
Assume that the formula holds for $n = j$ :
$(x+y)^j = \sum_{k=0}^{j} {j \choose k} x^{j-k} y^k$

Using this identity we need to show that it also holds for $n = j + 1$ .

Multiply both sides of the inductive hypothesis by $x + y$ :
$(x+y)^{j+1} = (x+y)\sum_{k=0}^{j} {j \choose k} x^{j-k} y^k$

Now we can split the summation like so:
$(x+y)^{j+1} = \sum_{k=0}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j} {j \choose k} x^{j-k+1} y^{k+1}$

Consume the first element of the first summation:
$(x+y)^{j+1} = x^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j} {j \choose k} x^{j-k} y^{k+1}$

Consume the last element of second summation:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j-1} {j \choose k} x^{j-k} y^{k+1}$

Shift the bounds of the second summation to match the first:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=1}^{j} {j \choose {k-1}} x^{j-k+1} y^k$

From here, we can factor the same elements:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} [x^{j-k+1} y^k] ({j \choose k} + {j \choose k-1})$

We will use the identity ${j \choose k} + {j \choose {k - 1}} = {{j + 1} \choose k}$ to simplify:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {{j + 1} \choose k} [x^{j-k+1} y^k]$

Note that ${{j + 1} \choose 0} x^{j + 1} y^0 = x^{j+1}$ , so we can insert first element of first summation back into the summation by setting lower bound to 0:
$(x+y)^{j+1} = y^{j+1} + \sum_{k=0}^{j} {{j + 1} \choose k} [x^{j-k+1} y^k]$

Apply similar reasoning for the upper bound to move $y^{j+1}$ inside the summation:
$(x+y)^{j+1} = \sum_{k=0}^{j + 1} {{j + 1} \choose k} [x^{j-k+1} y^k]$