How prove this sequence $a_{n}$ is $a_{n}=2n+1$ without mathematical induction? 
Let  sequence  $a_{1}=3$ and $$a_{n+1}=a^2_{n}-2na_{n}+2,n\ge 1$$
Find the $a_{n}$

My idea: 
since
$$a_{2}=9-6+2=5,a_{3}=a^2_{2}-4a_{2}+2=25-20+2=7,a_{4}=a^2_{3}-6a_{3}+2=49-42+2=9$$
so I inductive
$$a_{n}=2n+1$$
and it is easy use Mathematical induction to prove it
since
$$a_{n+1}=(2n+1)^2-2n\cdot (2n+1)+2=2(n+1)+1$$
My Question,This sequence have without mathematical induction methods?
such as this two  post. At first I thought to can't find other ways, but finally surprised someone gives three different methods:
How find this $n(n+1)a_{n+1}=n(n-1)a_{n}-(n-2)a_{n-1}$
,How find $a_{n}$ if the sequence $a_{n}=2a_{n-1}+(2n-1)^2a_{n-2},n\ge 1$
 A: Let $b_n = a_n - 2n$. Observe that $b_1 = 1$. We can substitute this into the given recurrence relation and get $$b_{n+1} + 2n = (b_n + 2n)\cdot b_n$$ In particular, this formula tells us: if for any $n$ we have $b_n = 1$, then $b_{n+1} = b_n$. Since $b_1 = 1$, it follows the sequence $\{b_i\}_{i=1}^{\infty}$ is constant. Hence $a_n = 2n + b_n = 2n + 1$.
A: What you want to prove is: 
$\forall n \in\mathbb{N}: a_n = 2n+1$.
Of course, one can convince oneself that this equation holds by several ways, e.g. by heuristics, by plugging in $2n+1$ into the recursive description or by arguing that some sequence is constant. But in every case one states that some property has to hold for every natural number (and this is obvious since the very claim you want to prove is a claim "for every natural number...").
For me, the most "induction hiding" version is "plugging in $2n+1$ into the recursive description". So I'll take this as an example where induction is hidden:
A proof could look like this:
An example
We have $a_{n+1} = a_n^2 - 2na_n +2$ for $n\geq 1$. Then $a_n = 2n+1$ since if we substitute:
$$\begin{aligned}
a_{n+1} &= (2n+1)^2 -2n(2n+1)+2\\&=4n^2+4n+1+2-4n^2-2n\\&=2n+3\\&=2(n+1)+1
\end{aligned}$$
it works.
Now, in fact, what have we proven? We have proven that:
$$\text{If $a_n = 2n+1$ (for some $n\in\mathbb{N}$) then $a_{n+1} = 2(n+1)+1$ (for this very $n$).}$$
Aha! This is the induction step. But still not the claim in question -- although almost.
A: You could calculate the first several values of $a_n$ and look at the differences:
$$
        \begin{matrix}
        3 &   & 5 &   & 7 &   & 9 \\
          & 2 &   & 2 &   & 2 &\\
        \end{matrix}
$$
The difference seems to always be $2$. This leads you to believe that the sequence is linear with the linear coefficient $2$. Finding that the constant term is $1$ then easy.
To check that this heuristically-derived answer is correct, substitute $a_n=2n+1$ into your recursion formula and see that it works.
Mathematical induction is often replaced by heuristics: see the book How to Solve It by George Polya for examples and details. Checking by substitution is a full and formal proof that the derived formula is correct. However, it does not prove that it is the only correct formula. Intuition tells us there is only one answer.
A: If you have a candidate solution you can just do this:


*

*Verify that $a_{n}=2n+1$ is a solution of the equation.
This is simple algebra. No induction.

*Argue that there can be only one solution for the equation, since it is deterministic:
Given $a_0$, the value of all $a_n$ follow.
