Proof by induction

Can anyone do the inductive step for these?

A sequence of positive integers U1, U2, U3, ... is defined by U1 = 1 and Un+1 = 3Un + 2 for N >= 1
Prove by induction that un =2(3^(n-1)) - 1

Prove that (x-y) is a factor of x^n - y^n for all integers n>=1 using the result x^(k+1) - y^(k+1) = x^k(x-y) + y(x^k - y^k)

Cheers.

Reply 1

AlphaNumeric

$u_{n+1} = 3u_{n}+2$ and $u_{n} = 2.3^{n-1}-1$
$u_{2} = 3u_{1}+2 = 5 = 2.3^{2-1}-1$
So true for first step. Assume true for n=k
$u_{k+1} = 3\big[2.3^{k-1}-1\big]+2 = 2.3.3^{k-1}-3+2 = 2.3^{k}-1$
This is exactly what you'd have if n=k+1, therefore inductive step proved.

Next one :

$x^{k+1}-y^{k+1} = x^{k}(x-y)+y(x^{k}-y^{k})$
Consider k=0, this implies that $x^{1}-y^{1}$ is divisible by (x-y). But then the expression tells you if $x^{k}-y^{k}$ is divisible by x-y then so is $x^{k+1}-y^{k+1}$ because you'd have
$x^{k+1}-y^{k+1} = x^{k}(x-y) + y(x-y)T$ where $(x-y)T = x^{k}-y^{k}$

You don't really need to do an inductive step, just realise what the expression tells you.

Reply 2

Cexy

Sure. For the first one, the base case is n=1, and it's easy to check that 2.3^1-1 - 1 = 1.

Then assume that u_n =2.3^n-1 - 1, and show that the formula holds for n+1:

u_n+1 = 3u_n + 2 = 3(2.3^n-1 - 1) + 2 = 2.3^{n+1 - 1} - 1

Thus if the formula works for n, then it works for n+1. But it works for 1, so it works for 2, and 3, and 4 etc, and so it is proved by mathematical induction.

Edit: Dammit George!

Latest

Trending

Articles for you

Mathematics degree personal statement example (2i) Imperial, UCL offers

Mathematics degree personal statement example (1l) Warwick offer

Personal Statement:Philosophy, Politics and Economics 16

Mathematics degree personal statement example (1d)

How The Student Room is moderated

To keep The Student Room safe for everyone, we moderate posts that are added to the site.

Try out the app

Continue on web

Proof by induction

Related discussions

Articles for you

How The Student Room is moderated