This seems like a trivial question, but I can't seem to wrap my head around the proof using induction.
Prove: $a_n=2a_{n-1}+a_{n-2}$, with initial condition $a_0=1$ and $a_1=1$, is an integer for $n \ge 0$
Here is what I understand so far...
Base case: $n=0$ and $n=1$
$a_0 = 1$ and $a_1=1$, which are both integers.
Assume:
$a_k=2a_{k-1}+a_{k-2}$ is an integer for some integer $k$, $k \ge 0$
Show:
$a_{k+1}=2a_{k}+a_{k-1}$ is an integer.
Now by our assumption $2a_{k}$ is an integer, but why would $a_{k-1}$ be considered an integer? In our assumption, we assumed that only $a_{k}$ is an integer, and two non-integers can easily add to form an integer. Can I show that, from the base case, $1+1$ will always form an integer closed under addition?
If you want to use the fact that $a_{k-1}$ is an integer, you actually can. This is another (equivalent) form of induction known as 'strong induction'.
Instead of just assuming $a_k$ is an integer, assume that $a_i$ is an integer for all integer $0\leq i \leq k$ . This way $a_{k-1}$ is also assumed to be an integer.
To use strong induction, you will obviously need to establish a 'stronger' base case, but that's fine, because you already have. You know that $a_0$ AND $a_1$ are integers.
Now complete the proof using the fact that the sum of two integers is an integer.
As an example to just show how strong induction works, lets take your problem with $a_2$
$a_2 = 2a_1 + a_0$, $a_1$ and $a_0$ are integers, so $a_2$ is an integer.
For $a_3$, $a_3 = 2a_2 + a_1$, we know both $a_2$ and $a_1$ are integers, so $a_3$ is an integer.
In this way, you can continue for all natural numbers and prove that $a_k$ is an integer for all integer $k\geq0$.