The problem consists of demonstrating through induction that $\forall a \in \mathbb{N}$ and $n\geq 0$ (where $n$ is an integer) $$(a^2+a+1)\mid(a^{n+2} +(a+1)^{2n+1})$$ That is, $a^2+a+1$ divides $a^{n+2}+(a+1)^{2n+1}$.
My work so far:
Considering the base cases, $n=0$ is trivial.
For $n=1$, since $a^2+a+1$ must divide $a^3+(a+1)^{3}$, there must exist $b \in \mathbb{N}$ such that $$b(a^2+a+1) = 2a^3+3a^2+3a+1$$ which turns out to be $$b = 2a+1$$ that is $$(2a+1)(a^2+a+1)=2a^3+3a^2+3a+1$$
For $n=2$ $$b(a^2+a+1) = a^4+(a+1)^5$$ $$(a^3+c_1a^2+c_2a+1)(a^2+a+1) = a^5 +6a^4+10a^3+10a^2+5a+1$$ which turns out to be $$b=a^3+5a^2+4a+1$$ that is $$(a^3+5a^2+4a+1)(a^2+a+1)=a^5+6a^4+10a^3+10a^2+5a+1$$ It is clear that this becomes a problem of factoring polynomials generated by $a^{n+2}+(a+1)^{2n+1}$ such that it always has a factor of $a^2+a+1$.
Now, assuming that this is true for $n=k$, that is $$b(a^2+a+1)=a^{k+2}+(a+1)^{2k+1}$$ $$\left(\sum_{p=0}^{2k-1}{c'}_pa^{2k-1-p}\right)(a^2+a+1)=a^{k+2}+(a+1)^{2k+1}$$ where $\sum_{p=0}^{2k-1}{c'}_pa^{2k-1-p}$ is a polynomial of degree 2 less than $(a+1)^{2k+1}$ and ${c'}_p$ are arbitrary (for now) coefficients of the factorization process.
Then, for $n=k+1$ $$\left(\sum_{p=0}^{2k+1}c_pa^{2k+1-p}\right)(a^2+a+1)=a^{k+3}+(a+1)^{2k+3}$$ idealy I would be able to extract a factor of $a^2+a+1$ from the LHS and relate the two polynomials, but I haven't been able to, also I can't see a way to use the assumption of $n=k$ being true to help prove the case for $n=k+1$ since the coefficients ${c'}_p$ and $c_p$ need not be the same. Working on the LHS $$a^2a^{k+1}+\sum_{p=0}^{2k+3}\binom{2k+3}{p}a^{2k+3-p}$$ $$=a^2a^{k+1} + a^2\sum_{p=0}^{2k+1}\binom{2k+3}{p}a^{2k+1-p} + \sum_{p=2k+2}^{2k+3}\binom{2k+3}{p}a^{2k+3-p}$$ adding and subtracting $a^2\sum_{p=0}^{k}a^{2k+1-p}$ and $a^2\sum_{p=k+2}^{2k+1}a^{2k+1-p}$ $$a^2\sum_{p=0}^{2k+1}a^{2k+1-p} - a^2\sum_{p=0}^{2k-1}\left(a^{2k+1-p}+a^{2k-1-p} \right) + a^2\sum_{p=0}^{2k+1}\binom{2k+3}{p}a^{2k+1-p} + \sum_{p=2k+2}^{2k+3}\binom{2k+3}{p}a^{2k+3-p}$$ extracting a factor of $a^2+a+1$ from $\sum_{p=0}^{2k+1}\binom{2k+3}{p}a^{2k+1-p}$ and changing the index of $\sum_{p=2k+2}^{2k+3}\binom{2k+3}{p}a^{2k+3-p}$ by a factor of 2 $$a^2\sum_{p=0}^{2k+1}a^{2k+1-p}-a^2\sum_{p=0}^{2k-1}\left(a^{2k+1-p}+a^{2k-1-p}\right) + \sum_{p=0}^{2k+1}\binom{2k+3}{p}a^{2k+1-p}(a^2+a+1) - \sum_{p=0}^{2k+1}\binom{2k+3}{p}a^{2k+1-p}(a+1)+ \sum_{p=2k}^{2k+1}\binom{2k+1}{p}a^{2k+1-p}$$ however I don't know how to continue from here since this is becoming a mess and I haven't been able to extract a factor of $a^2+a+1$ from all terms. The only thing I tried to accomplish is to have all terms with summation run from $0$ to $2k+1$, but seems to have failed.
Can somebody help me with the following steps of this proof?
Here is a different take based on linear recurrences.
Let $x_n = a^{n+2} +(a+1)^{2n+1} = a^2 a^n + (a+1)((a+1)^2)^n = a^2 A^n + (a+1)B^n$, with $A=a$ and $B=(a+1)^2$. Then, $x_{n+2}=(A+B)x_{n+1}-ABx_n$. The claim follows at once by induction if it holds for $x_0$ and $x_1$, which is simple to check.