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

Postgraduate Master's Loan - How to Apply

Student finance – how to apply

Postgraduate Doctoral Loan - How to apply

Smartphone apps that can help you revise for GCSE and A-level exams

Try out the app

Continue on web