Simple Induction

[dally165]

Hi all, I don't know why I need to do a Maths paper when i'm majouring in Computers.. anyway I have 2 induction problems (Proving or disproving propositions)..

1. For any integer n, n^2 - n + 19 is a prime number.
I only know how to do the first part which is subsituting n with 1.
Thus:

1^2 - 1 + 19 = 19 and yes 19 is a prime number so that's a tick.

next is to assume n as k so:

k^2 - k +19

then show:

(k+1)^2 - (k+1)+ 19

Then what?

Next is problem 2

2. For any integer n is lesser than or equal to 1 1 x 1! + 2 x 2! + 3x 3! + ... + n x n! = (n+1)! - 1

So first thing I do as usual is to substitue n with 1 so:

1 x 1! = (1 + 1)! - 1
and both are equal to 1

next is to assume the n is k thus: k x k! = (k+1)! - 1

Then show:
(k+1) x (k+1)! = (k+1+1)! - 1

Am I even on the right track? man am I slow..

So yeah.. please help me understand.. If I don't get this, then there's no way i'm gonna pass the mid-sem exam!
I have more problems than this but I want to focus on induction first before I move on to the next topic!

I don't know how to add symbols so sorry if it's a bit hard to read!!
Thanks!

 

[daon]

For #1, you should know there is no simple formula for computing a prime given a natural number. Try plugging some other numbers.

For #2, it seems you're going off track

You're assuming:
[1]\(\displaystyle \sum_{k=1}^n k(k!) = (n+1)!-1\)

You want to show:
[2]\(\displaystyle \sum_{k=1}^{n+1} k(k!) = (n+2)!-1\)

Take the given (what you assume to be true) and add \(\displaystyle (n+1)(n+1)!\) to both sides.

Can you show the following is equivilent to the above [2]?

\(\displaystyle \sum_{k=1}^{n} k(k!) + (n+1)(n+1)! = (n+1)!-1+(n+1)(n+1)!\)

 

[dally165]

I was wrong, ok it's supposed to be LHS equal to (n + 1)! right?

so now I'm trying to prove if (k + 1)! - 1 + [(k + 1)(k + 1)!] is equal to (k + 1)! - 1

how to you simplify if there's factorial involved? coz I can't go (k^2 + 2k + 1)! can I?
I'm really stuck..

 

[galactus]

2. For any integer n is lesser than or equal to 1 1 x 1! + 2 x 2! + 3x 3! + ... + n x n! = (n+1)! - 1

\(\displaystyle 1\cdot 1!+ 2\cdot 2!+ 3\cdot 3!+......+n\cdot n!+(n+1)(n+1)!=(n+1)!-1+(n+1)(n+1)!=\underbrace{(n+2)!-1}_{\text{here is what must be shown}}\)

ecce signum

I did not go through all the steps, but you see?.

 

[dally165]

Hmm I kind of understand that bit but I don't know what to do next.. i'm literally stuck..

 

[BigGlenntheHeavy]

First one: Forget the induction, just show a counter example to disprove the statement.

For any integer n, n^2 - n + 19 is a prime number.

Let n = 19, then 19^2 -19 +19 = 19^2 = (19)(19), a composite number.

Hence the statement is false by the counter example. QED

Second one:

After all is said and done, including the inductive hypothesis, we must show that:

(k+2)!-1 = (k+1)!-1+(k+1)(k+1)!
= (k+1)!+(k+1)(k+1)!-1
= (k+1)![1+(k+1)]-1
= (k+1)!(k+2)-1
= (k+2)!-1 QED

 

[galactus]

I agree with Glenn. That formula does not generate primes \(\displaystyle \forall \;\ n \in Z\).

For n=1, it does. But try n=2 and we get 21, n=3, we get 25, and so on. It generates a few primes, but not all.

Therefore, to disprove the statement, just provide one counterexample as Glenn done.

There is no formula that generates all primes. But a good one is \(\displaystyle n^{2} + n + 41\).

This generates primes for n<40.

 

[dally165]

Second one:

After all is said and done, including the inductive hypothesis, we must show that:

(k+2)!-1 = (k+1)!-1+(k+1)(k+1)!
= (k+1)!+(k+1)(k+1)!-1
= (k+1)![1+(k+1)]-1
= (k+1)!(k+2)-1
= (k+2)!-1 QED

Thanks for that but on your 2nd to 3rd step:
= (k+1)!+(k+1)(k+1)!-1
= (k+1)![1+(k+1)]-1 - how did you manage to remove the factorial off (k+1)(k+1)! ? How did you come up with that??

Thanks for everyone who helped!

 

[BigGlenntheHeavy]

I factored it out, for example:

(x+xy)-1 = x(1+y)-1, let x = (k+1)! and y = (k+1).

 

[dally165]

Also I have another question I'm stumbling on:

Show that if n is an integer and n^3 + 5 is odd then n is even
(a) by proving the contrapositive
(b) using a proof of contradiction

Here's what I got:

(a) So the statement I want to end up with is if n is an integer and n^3 + 5 is even then n is odd.. right?

(b) So n^3 = 2k - 5 = 5(k - 1)
In theory, any integer multiplied by 2 always comes out even. I have shown that n is both odd and even. Therefore n must be even when n^3 + 5 is odd.

So is it considered a contradiction??

 

[daon]

a) "If n is not even, then n^3+5 is not odd" ~ "If n is odd then n^3 + 5 is even."

b) You factored wrong. Assume "for the purpose of contradiction" that n is odd and contradict the assumption that n^3+5 is odd.

Hint: If n is odd then n=2k+1 for some integer k. Multiply out and simplify: (2k+1)^3+5

 

[BigGlenntheHeavy]

(a). If n is an integer and n^3+5 is odd, then n is even.

Contra-positive: If n is an integer and n is odd, then n^3+5 is even.

Proof: if n is odd, then n = 2k+1, k an integer, hence (2k+1)^3 +5 = 8k^3+12k^2+6k+1+5 = 2[4k^3+6k^2+3k+3]

Let 4k^3+6k^2+3k+3 = m, m an integer (multiplication and addition of integers is closed), ergo n^3+5 = 2m, 2m an even integer. QED

(b) Suppose not (contradiction).
If n is an integer and n^3+5 is odd, then n is odd.

If n is odd, then n = 2k+1, k an integer, ergo (2k+1)^3+5 is odd, but we already proved (see above) that (2k+1)^3+5 is

even, when n is odd. Hence the supposition is false and the original statement stands.

 

[dally165]

(b) Suppose not (contradiction).
If n is an integer and n^3+5 is odd, then n is odd.

If n is odd, then n = 2k+1, k an integer, ergo (2k+1)^3+5 is odd, but we already proved (see above) that (2k+1)^3+5 is

even, when n is odd. Hence the supposition is false and the original statement stands.

You mean by using contradiction it gets invalid?

I have more problems but before I move on, I'd like this to be checked:

Prove by induction:

1^2 + 3^2 + 5^2 ... + (2n - 1)^2 = n/3(2n-1)(2n+1)

n=1 LHS = 1^2 = 1 (duh) RHS = 1/3(2 - 1)(2 +1) = 1

So n=1 holds.
Assume: 1^2 + 3^2 + 5^2 + ... (2k - 1) = k/3(2k - 1)(2k + 1)
Show: 1^2 + 3^2 + 5^2 + ... (2k - 1)^2 + (2(k + 1) - 1)^2 =(k+1)/3(2(k+1) - 1)(2(k+1)+1)
or 1^2 + 3^2 + 5^2 + ... (2k - 1)^2 + (2k - 1)^2 = (k+1)/3(2k+1)(2k+3)

LHS = k/3(2k-1)(2k+1)+(2k+1)^2
= (2k+1)/3[k(2k-1)+3(2k+1)] = (2k+1)/3(2k^2 - k + 6k + 3)
= (2k+1)/3(2k^2+5k+3) = (2k+1)/3(2k+3)(k+1)

QED?

It looks correct to me but I want to confirm it

Also we moved on into Recursion and this is the question:

A sequence is defined recursively by a(low 1) = 1, a(low 2) = 3 and a(low k) = a(low k-1) + 2a(lowk-2) for k is greater than or equal to 3. Use a theorem to find an explicit formula for a(low k)

(low # means it is beside 'a' in the low position.. kind of like the opposite of a^1, a^2, a^k, etc...)

Below are the kind of examples the teacher gave us but I don't quite get it.

Example 1:

Consider the arithmetic sequence a, a + d, a + 2d, ...
Explicit definition t(low n) = a + (n - 1)d
Recursive definition t(low n) = t(low n-1) + d

Example 2:
Find explicit and recursive definitions for t(low n), for the sequence 5, 8, 11, 14,...
Explicit definition t(low n) = 3n + 2
Recursive definition t(low n) = t(low n - 1) + 3

Ok I could go on but it's not helping me answer the question above..

 

[BigGlenntheHeavy]

\(\displaystyle Does \ a_2 \ = \ 2 \ or \ 3?\)

 

[mmm4444bot]

Hello dally165:

I'm adding a comment about notation.

Those "low" numbers are called subscripts. (We use them to denote the positions of numbers in a sequence.)

We can type subscripts using the underscore character.

a_1 = the first sequence number

a_2 = the second sequence number

a_44 = the 44th sequence number

a_n = the nth sequence number

(There's also a subscript button in this forum, but it often screws up the display, so I can't recommend using it.)

Using an underscore to denote subscripts, here's what you typed for the recursive sequence definition:

a_1 = 1

a_2 = 3

a_k = a_(k-1) + 2 * a_(k-2) , for k > 2

Cheers,

~ Mark

 

[dally165]

Re:

Using an underscore to denote subscripts, here's what you typed for the recursive sequence definition:

a_1 = 1

a_2 = 3

a_k = a_(k-1) + 2 * a_(k-2) , for k > 2

Cheers,

~ Mark

Thanks for that! So yeah i've no idea how to even begin to answer that.. and I have this problem with family of sets as well.. i'm not too sure how to type it but i'll try my best.

Question: Let A_i = {1,2,3,...,i} for i = 1,2,3,...

Find:

[a] Ok I cant find any other images so it's like the one below but instead of an infinity symbol on the top, it's 'n'

Exactly the same as [a] (again it is a'n' instead of the infinity symbol) except it's an intersection instead of a union!

Sorry for the poor illustration! any input is much appreciated!!

 

[daon]

\(\displaystyle \bigcap_{i=1}^n A_i = \{1\} \cap\{1,2\} \cap\{1,2,3\} \cap... \cap\{1,2,3,...,n\}\)

What are the elements that appear in every one? That is what it means to be the intersection.

\(\displaystyle \bigcup_{i=1}^n A_i = \{1\} \cup \{1,2\} \cup \{1,2,3\} \cup ... \cup \{1,2,3,...,n\}\)

When you put all of these sets together into one big set, what are the distinct elements? Thats taking a Union.

 

[dally165]

Oh I see..

So the answer is the same for both??

= {1,2,3,...,n}?

Cause those are the elements that intersect and the same for union when all elements are put together?

Am I right?

 

[Mrspi]

Oh I see..

So the answer is the same for both??

= {1,2,3,...,n}?

Cause those are the elements that intersect and the same for union when all elements are put together?

Am I right?

No.

The intersection of the sets {1}, {1, 2}, {1, 2, 3}, ...... is the set of elements which ALL of these sets have in common...please look carefully. What element(s) are in ALL of these sets?

 

[dally165]

Oh I see..

So the answer is the same for both??

= {1,2,3,...,n}?

Cause those are the elements that intersect and the same for union when all elements are put together?

Am I right?

No.

The intersection of the sets {1}, {1, 2}, {1, 2, 3}, ...... is the set of elements which ALL of these sets have in common...please look carefully. What element(s) are in ALL of these sets?

Hmmm Ok for [a] = {1}
and for = {1,2,3,...,n}

right? right??