Let $F=\mathbb{F}_{q}$ be a finite field of order $q=2^{n}$ and let $\beta$ be a primitive element of $F$. I would like to prove that if $q>4$, then for each $1\leq i \leq \frac{q-2}{2}$, there exists a $1\leq j \leq \frac{q-2}{2}$ such that $j \neq i$ and $$Tr\left(\frac{\beta^{i+j}}{1+\beta^{2i}}\right)=1,$$ where $Tr: F\to \mathbb{F}_{2}$ is the trace map.
I have checked using a computer that this is true for $q$ up to $128$, however I am not sure how to proceed with proving such a statement.
Could anyone give any hints?
Many thanks!
Let $m(x)$ be the minimal polynomial of $\beta$ over $\Bbb{F}_2$. Then we know that $m(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+1$. Furthermore, because $m(1)\neq0$ we also know that $m(x)$ has an odd number of non-zero terms. Denote by $S$ the set of indices $k=0,1,2,\ldots,n$ such that the term $x^k$ appears in $m(x)$ with coefficient $1$. In other words $$ m(x)=\sum_{k\in S}x^k. $$
For all sufficiently large $n$ the allowed range of exponents $j$ has a run of length $n$ such that $i$ is not in that range. Let $[\ell,\ell+n-1]$ be such a run. Let us denote $$b(j)=Tr\big(\frac{\beta^{i+j}}{1+\beta^{2i}}\big).$$ I claim that there exists at least one $j, \ell\le j<\ell+n$ such that $b(j)=1$.
Assume contrariwise that $b(j)=0$ for all $j\in[\ell,\ell+n-1]$. The key is that for any exponent $t$ we have the recurrence relation $$ \sum_{k\in S}b(t+k)=0. \qquad(*) $$ This is because $$ \sum_{k\in S}b(t+k)=\sum_{k\in S}Tr\big(\frac{\beta^{i+t+k}}{1+\beta^{2i}}\big)= Tr\big(\frac{\beta^{i+t}}{1+\beta^{2i}}m(\beta)\big)=Tr(0)=0. $$ Recall that $0$ and $n$ are both in the set $S$. Our contrapositive assumption and the equation $(*)$ applied to $t=\ell$ imply that $b(\ell+n)=0$ also. Applying $(*)$ to $t=\ell+1$ then implies that $b(\ell+n+1)=0$, too. Continuing in this way we see that together with the contrapositive assumption equation $(*)$ implies that $b(j')=0$ for all $j'\ge\ell$ up to $j'=\ell+q-2$. But, because $\beta^i/(1+\beta^{2i})\neq0$ this implies that the trace vanishes on all of $\Bbb{F}_{2^n}^*$. This is known not to be the case.
The so called linear complexity (=depth of the shortest recurrence relation) of your sequence is $n$, and a general fact of sequences generated by such a recurrence relation is that they cannot have a run of $n$ zeros unless the entire sequence consists of zeros.