Exploring Two Number Theory Problems: A Challenge for Mathematicians

[Fisicks]

I have wrestled with the following two problems for a couple of hours each and have been successful. Now I am interested in how a more experienced mathematician would go about solving these.

I encourage you to look past my lack of latex skills (lol), and do your best with the attachment I poorly put together.

A note about the second problem, If anyone is unaware F denotes the Fibonacci numbers and L denotes the Lucas numbers. Second, the term on the left side is a little blurry but it says the 2n Fibonacci number. Also I challenge you to solve this second problem without strong induction. Which I semi-managed to do. I proved a secondary result with strong induction then used that result to use regular induction on the main problem.

 

[Tedjn]

I have not completely worked out the first one, but I would try to form a one-to-one correspondence between the nonzero integers in base 3 and the nonzero integers in the form given by the problem.

For the second, induction seems like a good way to go. However, if you have derived the closed form formulas for both, the result follows immediately.

 

[rasmhop]

First problem:

The way I proved it was to prove for a fixed s, every integer in n with absolute value less than or equal to $3^0 + 3^1 + \cdots + 3^s$ can be expressed uniquely in the form:
$$\sum_{j=0}^s c_j 3^j$$
with $c_j \in \{-1,0,1\}$ (I don't require that c_s is non-zero, since if it is we can just pick the largest j with c_j non-zero, and if all c_j are 0, then we are in the exceptional case where n=0).

First proving uniqueness suppose:
$$\sum_{j=0}^s c_j 3^j = \sum_{j=0}^s d_j 3^j$$
with $c_j, d_j \in \{-1,0,1\}$. You can show $c_j=d_j$ for all j.

Let
$$C_s = \left\{\sum_{j=0}^s c_j 3^j | c_j \in \{-1,0,1\}\right\}$$
Try to work out:
1) How many elements are in C_s?
2) What is the maximum and minimum element of C_s?
When you answer these you should be able to show that C_s = {-N,-N+1,...,N-1,N} where
$$N = 3^0 + 3^1 + \cdots + 3^s$$

 

[rasmhop]

Second problem:

I assume you know the identity (otherwise you can easily show it):
$$L_n = F_{n-1} + F_{n+1}$$
Then your identity is equivalent to:
$$F_{2n} = F_nF_{n+1}+F_nF_{n-1}$$
Now let us strengthen to induction hypothesis to also say:
$$F_{2n+1} = F_{n+2}F_{n+1}-F_nF_{n-1}$$
Then you can perform a normal inductive argument (there are some slightly messy calculations, but unless you already know some identities involving Lucas numbers and Fibonacci numbers I don't immediately see a cleaner way).

 

[Fisicks]

Thanks for the reply rasmhop. One question.

In one element of C_s, there are S terms. Each term may be assigned either -1, 0, or 1. Thus there are 3^s combinations and C_s includes 3^s elements. But if your right, C_s should include 2N+1 elements. Therefore I can conclude that not every integer (absolute value) less than N can be expressed in your form.

Who is at fault here?

 

[rasmhop]

In one element of C_s, there are S terms. Each term may be assigned either -1, 0, or 1. Thus there are 3^s combinations and C_s includes 3^s elements.

0,1,2,...,s are s+1 numbers so there are s+1 terms, and thus C_s contains 3^(s+1) elements.

The maximal value of an element of C_s is:
$$N=3^0 + 3^1 + \cdots + 3^s = \frac{3^{s+1}-1}{3-1} = \frac{3^{s-1}-1}{2}$$
and the minimal is -N. 2N+1 = 3^(s+1).

 

[Fisicks]

Thanks for showing me the light lol. I always forget about that zero, which hurt me a lot on exams working with convergence.