Mathematical induction Definition and 218 Threads

Recall that the fibonacci sequence is defined as { f0=0; f1 = 1 and {fn = f n - 1 + fn -2 for n 2 Prove by generalized mathematical induction that fn = 1/sqrt(5)[ϕn - (-ϕ)-n] where ϕ = [1+sqrt(5)]/2 is the golden ratio.. (This is known as de Moivre's formula.) So...

Hey! I've just started to learn some mathematical induction and it's proving quite tricky. Hopefully someone could help me out a little with my questions! I don't know how to format question on this forum but I'll try my best to accurately represent it: n sigma i * 2^i = (n-1) * (2^n+1) + 2...

Here is the question: I have posted a link there to this thread so the OP can see my work.

With mathematical induction i should prove that is true for all natural numbers:http://img.tapatalk.com/d/13/10/18/u6epesu5.jpg Im sorry beacuse i have inserted an image,but I am still not used to write it in [MATH] here...

Homework Statement Prove; n^2 > n+1 for n = 2,3,4 by Induction Homework Equations The Attempt at a Solution p(n)= P(2) 2^2> 2+1 --> 4>3 Induction step: P(n+1): (n+1)^2 > (n+1) +1 (n+1)^2> n+2 n^2 + 2n + 1 > n+2 | -n n^2 +n + 1> 2 | -1 n^2 +n > 1 Is this correct, and how...

Homework Statement Find all natural numbers such that 2n ≥ (1+n)2, and prove your answer. 2. The attempt at a solution I can see this is true for n=0 and n>5. I try to prove this using induction as follows 20 =1≥ 1=(1+0)2 base case: 26 =64≥ 49=(1+6)2 so it is true for n=6 and suppose 2n...

Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of introducing mathematical induction? I need something which will have an impact. Are there any real...

Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of introducing mathematical induction? I need something which will have an impact. Are there any real...

Homework Statement (1 1)^n = (1 n) (0 1) (0 1) Prove this through mathematical induction. Homework EquationsThe Attempt at a Solution I've replaced n with 1, so I've done that far. Then I said k = n. Then replaced all n with (k+1). I'm really stuck...

Verify that 1(1!)+2(2!)+...+n(n!) = (n+1)! - 1 is true using induction This problem has me stumped...

Homework Statement Prove the theorems using mathematical induction. \forall n \in N, n\geq 4 \rightarrown2\leq n! Thanks in advance! Homework Equations The Attempt at a Solution First, check the base case which is n=4. \Rightarrown=4\geq4-True \Rightarrow42\leq4*3*2*1...

Let A(subn) = {1,2,3,...,n} For any set B, let P(subk)B=the set of all subsets of B with exactly k elements. For example, P(sub2)({1,2,3})={{1,2},{1,3},{2,3}}. A) Find P(sub2)(A(sub1)), P(sub2)(A(sub2)), P(sub2)(A(sub4)), and P(sub2)(A(sub5)) B) Use mathematical induction to prove that the...

Hi all, I am revising on Proof by mathematical induction and I have came across a question I haven't found a way to work it out. \sum_{r=1}^n r(r!) = (n + 1)! -1 I understand the steps of proving by mathematical induction question. The ! is causing the confusion.

Hi all, I am so sorry I don't know whether to post this. I am revising Proof by mathematical induction Further maths using an Edexcel FP1 book. The following is from chapter 6 example 3. I know how to work Proof by mathematical induction it is part of the example that I don't understand. I...

Please refer to the image attached. Where does the > 2 x k come from? Based on the proposition, shouldn't it be > k+1?

Homework Statement 1-1/2+1/4-1/8+...nth term= [(2^n-(-1)^n)]/3(2^(n-1))] I just can't get the nth term. I realize that the denominator should be 2^(n-1) and that, because the sign constantly changes there needs to be something like -1^n so I came up with the equation -1^n/-2^(n-1) but this...

Hello I'm learning about proofs and in my book there's a sect. On mathematical induction. And I'm trying understand why this makes it true for all values. 1+3+5...2n-1=n^2 Suppose that the formula is known to be true for n=1, and suppose that as a result of assuming that it is true for n=k...

Prove by mathematical induction: (2n)! < (2^(2n))*(n!)^2 , for all n=2,3,4... I know that to start you must prove that it is true for n=2, (2*2)! = 24 < 64 = (2^4)(2!)^2 Then you assume that n=k and show tha n=k implies that n=(k+1) (2k)! < (2^(2k))*(k!)^2 ... At this point I...

Hi all, I've been struggling with a large piece of coursework. been quite stressed latley and now I am struggling while aproaching my deadline. i need help answering this question. Use mathematical induction to show that S(n) = 3 × 2 n-1 -2 is the solution for the recurrence relation: T(n)...

How do I prove a formula/rule or something by mathematical induction? Please give me a few examples or resources and explain it as best you can because I think I'm messing up some how.

Prove that: 1 + 1/√2 +...+ 1/√n < 2√n Work: So I've done the base case of n = 1, and I've set up the Indutive hypothesis as assuming n=k as 1 + 1/√2 +...+ 1/√k < 2√k and for the inductive step: 1 + 1/√2 +...+ 1/√k + 1/√(k+1) < 2√k + 1/√(k+1) now I'm having trouble trying...

Hello folks, I have an induction problem that I have been working on, and I am at my wit's end. If anybody could provide me with a nudge in the correct direction, I would greatly appreciate it. I have attempted to factor out a number of terms to find something remotely intuitive here to present...

Homework Statement Here is this problem: I have the solution http://www.proofwiki.org/wiki/Leibniz%27s_Rule/One_Variable This is where I get stuck.. Where it says: 'For the first summation, we separate the case k=n and then shift the indices up by 1.' Why does this lead to the...

Suppose we want to prove that: 1/2 * 3/4 ... 2n-1/2n < 1/sqrt(3n) for all positive integers. (a) Show that if we try to prove this inequality using mathematical induction, the basis step works, but the inductive step fails.(b) Show that mathematical induction can be used to prove the stronger...

Homework Statement Prove that for all n>1, P(n) :1 + 1/2 + 1/3 +...+1/n = k/m where k is an odd number an m is an even number.Homework Equations The Attempt at a Solution 1)Base Case n =2 P(2) = k/m 3/2 = k/m which is true. 2) Inductive Step Assume P(n) is true for some arbitrary n. 3)...

Homework Statement show n3 + n < 3n for all n >= 4 Homework Equations The Attempt at a Solution I.H : n3 + n < n for all n >= 4 3(n3 + n) < 3(3n) then (3n+1) = 3 x 3 n > 3((n3) + n ) by I.H...

Homework Statement I am working on a mathematical induction problem, where I need to prove: (1 - (-7) ^ (k + 2)) / 4Homework Equations (1 - (-7) ^ (k + 1)) / 4 + 2(-7) ^ (k + 1) The Attempt at a Solution So I just need to add the two items in section two above. Now I know I need a common...

Homework Statement Use mathematical induction to prove the following statements are true for n≥1 a) 1^2+3^2+5^2+...+(2n-1)^2= [n(4n-1)]/3 Homework Equations The Attempt at a Solution Attempt at showing for n+1 is true: n[4(n+1-1)]/3+ 2[k+1-1)^2

Homework Statement Let F: N->N be defined by f(1)=1 and f(2)=2 and f(n+2)=1/2(f(n+1)+f(n)) Use Theorem 1.3 to prove that 1<=f(n)<=2 for all n in N Homework Equations For each n in N let P(n) be a statement about the positive integer n. If a) P(1) is true, and b) for k>1, P(k) is...

what is mathematical induction? explain with an example.

Homework Statement Prove that \frac{1}{n}\sum_{i=1}^n x_i\geq {(\prod_{i=1}^n x_i)}^{1/n} for positive integers n and positive real numbers x_i Homework Equations There is also a hint. It states that it does not seem to be possible to prove it directly so you should prove it for n=2^m...

Prove that f(n) = 4^n + 6n - 1 is divisible by 9 for all positive integers of n. I've proved this by considering that f(k) is divisible by 9, i.e f(k) = 4^k + 6k -1 = 9m where m is some integer. Rearranging to give 4^k = 9m - 4k + 1 and then considering f(k+1) = 4^(k+1) + 6(k+1) - 1 then...

Hi, I'm currently taking Discrete Mathematics and I'm working on a mathematical induction problem that's a little different than usual because it has a summation in it. What I basically want to know is did I do parts A and C correctly? Homework Statement Homework Equations The Attempt at a...

I want to now the answer of this question and I think it relates to mathematical induction. The question is: -Suppose is a natural number. In how many ways can we place numbers around a circle such that each number is a divisor of the sum of it's two adjacent numbers? Who can answer this...

Hello! First of all I have like 5 exercises I don't quite understand so will it be a problem if I create 5 new topics in the next 24h? Homework Statement Prove, by using mathematical induction that if x+1 \geq 0 then (1+x)^n \geq 1+nx. Homework Equations The Attempt at a Solution Basic step...

Hello, I am having trouble solving this problem. Maybe I'm just overreacting to it. In my two semesters in discrete math/combinatorics, I've never seen a problem like this (with two summations) and been asked to prove it. Can some one help? \sum^{n}_{i=1} i^3 = \frac{n^2(n+1)^2}{4} =...

Homework Statement Hello! This is I want to prove using Mathematical Induction: 1+3+5+...+(2n-1)=n^2. The problem is: I don`t understand very much about Mathematical Induction :(Homework Equations The Attempt at a Solution Suppose n=1. Then 1=1. Now suppose 1+3+5+...+(2n)=(n+1)^2. Then...

Homework Statement I am asked to prove: 2n < (n+1)! , where n≥2 The Attempt at a Solution Base step: set n=2, then test 22 < (2+1)! 22 = 4 (2+1)!= 3! = 3(2)(1) = 6 so 4 < 6 , which is true. Induction hypothesis is 2k < (k+1)! Using this, prove 2(k+1) < [(k+1)+1]! = (k+2)! Attempt to...

I am currently exploring if whether or not a fourth dimension exists or can be drawn. According to my professor, I have to use mathematical induction. I know that 2^n is the equation and "n" equals the dimension. Therefore 2^1 is 2. The first dimension is a line with 2 terminal points...

Homework Statement (1/2!)+(2/3!)+(3/4!)+...+(n/(n+1)!) a) calculate for a few small values of n. b) Make a conjecture about a formula for this expression c)Prove your conjecture by mathematical induction. Homework Equations The Attempt at a Solution So for the first part I just used values...

Hey guys I am in precalculus right now and we just started picking up mathematical induction. Our teacher assigned us a problem that I am stumped over and I tried looking all over for a clear explanation online but I can't find anything remotely helpful. The question is: Use mathematical...

1. Define a sequence of numbers in the following way: a[k]=a[k-1]+a[k-2]+a[k-3] for k≥3, s.t. a[0]=1, a[1]=2, a[2]=3, a[3]=6... *The numbers in brackets will be subscripts for the whole problem Prove that a[n]≤2^n using complete mathematical induction. This is what I have so far. We'll use...

hi this question i just cannot do. i have no idea where to start: a student is trying to recall the formula for the sum of cubes of consecutive numbers. she thinks it may be (n^3(n+1)^3) /8 or (n^2(n+1)^2)/4 . show by counter example one is incorrect and the other is correct by induction...

I am having trouble proving these. I cannot figure out how to get to the conclusion. Here is my attempt. The stuff in red is just side work and is not part of the proof. I always get stuck on these types of problems, can someone offer some tips on how to approach these kind of problems in...

Hi, Some times the starting point in MA confuses me, for example (\sum_{i=1}^ni)^2=\sum_{i=1}^ni^3 have we start with 2 or it is enough to show it when n=1 Thanks in advance.

A question I'm working on and my math book doesn't clarify the answer well enough for me to follow. I'm having some issues at getting the math symbols to work correctly so bare with me!Prove by mathematical induction that if A1, A2, ..., An and B are any n + 1 sets, then: Base step = n = 1 so...

I have an idea of what to do and I have reached the stage but when i am at final stage- I am struggling to simplify as i simply don't understand (1/2)+(2/2^2) +(3/2^3)+...+ (n/2^n) = 2 - (n+2/2^n) so I have done p(k) and p(k+1) this gives me p(k) (1/2)+(2/2^2) +(3/2^3)+...+ (k/2^k)...

prove by induction that, 1) a^(m+n) = a^m + a^n 2) (a^m)^n=a^(mn) 2. Homework Equations -- mathematical induction 3. The Attempt at a Solution the equations hold for a = 1. let's say the equation hold for a = s; then s^(m+n) = s^m + s^n now for a = s+1; (s+1)^(m+n) = (binomial expansion of...

Homework Statement Show that it is possible to arrange the numbers 1, 2, ... n in a row so that the average of any two of these numbers never appears between them. [Hint: Show that it suffices to prove this fact when n is a power of 2. Then use mathematical induction to prove the result when n...

Homework Statement Suppose a and b are real numbers with 0 < b < a. Show that, if n is a positive integer, then a^n - b^n \leq na^{n-1}(a-b) Homework Equations The Attempt at a Solution I'm trying to show this by induction. Let P(n) be the proposition that a^n - b^n \leq na^{n-1}(a-b)...