# Eulers Approximation Inductive Proof

Alright so I am having some difficulty with an inductive proof. I am attempting to prove the following:

Given that the Euler Method is described by the given recursive formula:

$y_{n} = y_{n-1} + h f(x_{n-1}, y_{n-1}), n = 1, 2, 3, ….$

Show that the Euler Approximation $y_{n}$ can be represented by the following formula:

$y_{n} = ( 1 + \frac{1}{n})^{n} , n = 1, 2, 3, ….$

Given that:

$y' = y$ , $y(0) = 1$, and $h = \frac{1}{n}$

Proposed Solution:

Base Case (first re-write the recursive definition as $y_{n} = y_{n-1} (1 + \frac{1}{n})$ to increase clarity)

Let n = 1

$y_{0} (1 + \frac{1}{1}) = (1 + \frac{1}{1})^{1}$

$1 \cdot (1 + \frac{1}{1}) = (1 + \frac{1}{1})$

2 = 2

So the base case checks out.

Inductive Hypothesis

Now assume the following:

$y_{k – 1} (1 + \frac{1}{k}) \Rightarrow (1 + \frac{1}{k})^k \space \space \forall k \in Z^{+}$

Show that: $y_{k} (1 + \frac{1}{1+k}) \Rightarrow (1 + \frac{1}{k+1}) ^{k+1}$

And here is my problem because if I replace $y_{k}$ with $(1 + \frac{1}{k})^k$ I get the following:

$(1 + \frac{1}{k})^k \cdot (1 + \frac{1}{k+1}) ^{k+1} \nRightarrow (1 + \frac{1}{k+1}) ^{k+1}$

Can someone spot what I’m doing wrong?

-

The error is in your first line. Induction is on $k$, not on $n$, which remains fixed. The first line should be:
Base Case. (first re-write the recursive definition as $y_{k} = y_{k-1} (1 + \frac{1}{n})$ to increase clarity)