Need help with this proof

[true osprey]

So the question is "Prove that Un <= 2^n for all n>=0"

But no matter how many times i do it, i always get "2^(n+1) <= 2^(n+1)" which is technically true but i don't think that it's what i am supposed to get, any help ?

[true osprey]

I know i'm going to use this formula at some point (pretty obvious) but that's how i end up getting this weird result

I know this is not rigourious AT ALL and the redaction is probably wrong by english maths standards because i don't know how to do "maths in english" but it's just to show you my train of thought

[proven anchor]

why don't you keep u_{k+1} as it is and by substituting the inequality for each u_{i} , i<=k, you get u_{k+1} <= 1+ 2+ ... + 2^{k}, simplifying which gives you the right result

[dry maple]

I think it is just from the definition of the sequence we have
u(n+1)=(u(0)+...+u(n-1))+u(n)
=u(n)+u(n)=2u(n) starting from n=1. So, u(n)=2^(n-1) as u(1)=1=2^0.

[true osprey]

Yes, Un= 2^(n-1) is really easy to demonstrate but i am having a hard time with inequalities, i'll try F's method

[true osprey]

i don't get it, like i juste replace 2^(k) with the sum ? Isn't it what we're trying to prove or is there someting i did not understand ?

[dry maple]

We can prove it by induction. For k=0 it is true. Suppose that u_k<=2^k for all k<=n. Then we have
u(n+1)=u(0)+u(1)+...+u(n)<=1+2+...+2^n
=2^(n+1)-1<2^(n+1).

[true osprey]

That's what i'm trying to do but somehow i don't get the same result because 1+2+...+2^n = 2^(n)-1 that cancels with U_0, that's why i'm left confused

[dry maple]

this 1+2+...+2^n = 2^(n)-1 is not true

1+2+...+2^n = 2^(n+1)-1 is true. Note the differences

[true osprey]

yes my bad, that's what i meant, so what i wanted to say is that i get U_0+2^(k+1)-1 which is equal to 2^(k+1)

[dry maple]

you dont need that, This is if you want to prove that u(n)<=2^(n-1) which is in fact true. In my previous message i've given the full induction proof for that weaker problem that is in your initial statement

[true osprey]

ooooooh okkk i get it now, sorry for being so slow